Binary Search Algorithm

Consider we have the following array sorted in ascending order.

Suppose we have to search 29 in the above array. One way to find 29 is to check every element from the first index till we find 29. This linear search takes O(n) time complexity.

We can actually search 29 in less time complexity using the binary search algorithm.

Let’s see how it works.

1. Define the first index as left and the last index as right. Then, find the midpoint of the first and last index.
2. If the midpoint is equal to the number we are searching for (target), then return the midpoint and stop the search.
3. If the target is greater than the midpoint then only search to the right of the midpoint. So, update the value of left as midpoint + 1.
4. If the target is less than the midpoint then only search the left of the midpoint. So, update the value of right as midpoint — 1.
5. Repeat step 1 to 4 till the element at the left is smaller than the element at the right.

Let’s see it with an example:

Define the first index as left and the last index as right.

Find the midpoint of the first and last index. [(first index + last index) / 2]

Check if the element in the mid is our target.

As mid is less than target, it means target is at right of mid. So, we only have to check the right side of mid.

So, update the value of left as mid + 1.

Again find mid.

Check if the element in the mid is our target.

As mid is greater than target, it means target is at the left of mid. So, we only have to check the left side of mid.

So, update the value of right as mid — 1.

Again find mid.

As mid is equal to target, stop the search.

Target value is at index 5.

Time Complexity : O(logn)

Code

public class SearchElement {
public int search(int[] nums, int target) {
int mid = (0 + nums.length - 1) / 2;
int index = -1;
  if (target == nums[mid]) {
   index = mid;
  }
else if (target > nums[mid]) {
for (int i = mid + 1; i < nums.length; i++) {
    if (target == nums[i]) {
     index = i;    }
   }
  } else {
   for (int i = 0; i < mid + 1; i++) {
    if (target == nums[i]) {
     index = i;
    }
   }
}
  return index;
}
public static void main(String[] args) {
SearchElement obj = new SearchElement();
  int arr[] = { -1, 0, 3, 5, 9, 12 };
  int index = obj.search(arr, 9);
  System.out.println(index);
 }
}