Binary Search Implementation in Java


Hello Buddies

Let's implement binary search in java this time.
Like linear search , it also works with sorted collections.

The term binary is used to signify the process of splitting the search operation in 2 parts.
This process will be repeated until the element is found.

So what decided which part of the splitted collection has to be used.

It's a simple logic. Since the collection is already sorted, we can use the mid element everytime to discard the side having greater elements.

public class BinarySearch {

public static void main(String[] args) {

int[] sortedArray = { 1, 2, 3, 4, 9, 99, 100 };
int element = 99;
int idx = findIndex(sortedArray, element);
System.out.println("Index : " + idx);
}
private static int findIndex(int[] sortedArray, int element) {

int low = 0;
int high = sortedArray.length;

while (low < high) {
int mid = (low + high) / 2;

if (element < sortedArray[mid]) {
high = mid - 1;
} else if (element > sortedArray[mid]) {
low = mid + 1;
} else {
return mid;
}
}
return -1;
}


}


Some points to consider -

Worst-case performance         O(log n)
Best-case performance         O(1)
Average performance         O(log n)
Worst-case space complexity O(1)

Source : Wiki

Happy Coding!

No comments:

Post a Comment

Featured post

Oracle SQL Scheduled Jobs - An Interesting Approach

  Oracle SQL Scheduled Jobs A DB Scheduler is the best way to automate any backend database job. For instance, if you want to process the p...