Thursday, 23 March 2017

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!

Featured post

JAVA based project, that can be used to hit DB using JDBC, from WSO2 ESB

Hi Buddies, Here is a small project that will enable you to hit MySQL DB using WSO2 ESB - https://github.com/namitsharma99/customM...

Popular Posts