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!

Linear Search Implementation in Java

Hello Buddies

Let's implement a simple linear search.
As the name suggests, it will traverse in 1D and it keeps on iterating until the element is found.

public class LinearSearch {

public static void main(String[] args) {

int[] sortedArray = { 1, 2, 3, 4, 9, 99, 100 };

int element = 999;

int idx = findIndex(sortedArray, element);

System.out.println("Index : " + idx);

}

private static int findIndex(int[] sortedArray, int element) {

for (int i = 0; i < sortedArray.length; i++) {

if (sortedArray[i] == element) {

return i;

}

}

return -1;

}

}

Some details to keep in mind -

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

Source : Wiki 

Happy Coding!