What is Binary Search?

Given a sorted list of integers, how would you find a specific value in that list? The simplest method would be a type of linear search that would start with the first item and check each item in the list for the value. This method is sure to find the value eventually, but if the last item in the list is the value you’re searching for, then the search will have to check every single item. This means that in the worst case this search is going to run in O(n) time.

A better method is binary search, which cuts the time complexity down to O(log n).

The search works basically the exact same way you find a page in a book. If you wanted to find page 327 in a book with 786 pages you would:

· Open the book near the middle

· If the page you landed on is larger than 327, then the right side of the book is ignored, and you open the book near the middle between the current page and the first page of the book.

· If the page you landed on is smaller than 327, then the left side of the book is ignored, and you open the book near the middle between the current page and the last page of the book.

· This process is repeated with the number of pages to be searched cut in half with each step until the page that is needed is found.

This would have taken 8 comparisons to find the value using Binary Search. Whereas a linear search would have taken 327 comparisons.

Here is an illustration of the algorithm searching for the number 46 in the list 1, 4, 5, 7, 8, 11, 17, 24, 32, 46:

In each step, the relevant portion of the array is reduced approximately in half.

Here is a java implementation:

public static int BinarySearch(int [] arr, int targetValue) {
   int start = 0;
   int end = arr.length -1;
   while(start <= end) {
      int mid = (start + end) / 2;
      if(arr[mid] == targetValue) {
         return mid;
      }
      if(arr[mid] > targetValue) {
         end = mid -1;
      }else {
         start = mid +1;
      }
   }
   return -1;
}

Here is some sample data using the BinarySearch method defined above:

public class BinarySearch {
   public static void main(String[] args) {
      int[] intArr = {1,2,3,4,5, 52 ,68, 69, 81, 1004};
      System.out.println(BinarySearch(intArr, 1004));
      System.out.println(BinarySearch(intArr, 1));
      System.out.println(BinarySearch(intArr, 52));
      System.out.println(BinarySearch(intArr, 6));
   }
}

Which outputs:

9
0
5
-1