Binary Search in Java with Example

It is an algorithm that searches for an element in a sorted array and it follows Divide and Conquer algorithmic model.

Dictionary is the best example for Binary Search, since the words are in alphabetical order we don’t need to search each page by page for a word. Just, we will compare the word whether it is on front or back portion of the book and we will keep comparing till we find the word. Similarly, binary search performs the search for an element in a sorted array.

Consider if X is an element to be searched in an array, then binary search performs the following:

1. Compare X with the middle element


2. If X matches with middle element, return the index of element


3. Else, if X is greater than the mid element, then X can only lie in right half subarray after the mid element. So, repeat for right half


4. Else (X is smaller), repeat for left half

Note: In order to perform Binary Search, the array must be a sorted one.

Implementation of Binary Search

public class BinarySearch{
 
   public static void main(String[] args){
      int[] arr = new int[] {1, 2, 3, 4, 5, 6};
      int X = 6;

      int index = binarySearch(arr, X);
      if(index == -1) {
         System.out.println("Element not found");
      }else {
         System.out.println("Element found at index:"+index);
      }
  
   }
 
   private static int binarySearch(int[] arr, int X){
      int low = 0;
      int high = arr.length - 1;
  
      while(low <= high){
         int mid = (low + high)/2;
   
         if(X == arr[mid]){         // If element found, return index
            return mid;
         }else if(X > arr[mid]){    // If X is greater than Mid element
            low = mid + 1;
         }else{                     // If X is smaller than Mid element
            high = mid -1;
         }
      }
  
      return -1;   // If element not found, return -1
   }

}

In the above program, we have a sorted array of elements arr[ ] and, where X is the element to be searched. The binarySearch(int[ ], int) method initially checks X with the mid element in the array. If X matches with mid element then it returns index of mid element and search ends. If X is greater than mid element then there won't be any comparisons required to check in the first half of array, so search continues with the second half of array. If X is smaller than mid element then there won't be any comparisons required to check in the second half of array, so search continues with the first half of array.

For each iteration, X is compared with mid element and returning its index if matches. Else, reducing the size of array to half by eliminating elements at either left or right half of sub array and this process continues till the size of sub array to zero, nothing but no more elements to test. At the end if X is not equal to mid element in any of the sub array then it returns -1 as the indication of element X is not found in the array.

Thus, the binary search algorithm can be implemented to perform the search of an element in a sorted array.

Time Complexity

Consider a sorted array of 1023 elements. As the binary search algorithm will eliminate half of the array for each comparison, so dividing number of elements by 2 is equivalent to one comparison. So, 1023(2¹⁰ - 1) divided by 2 yields only 10 comparisons, 1,048,575(2²⁰ - 1) divided by 2 yields only 20 comparisons. So, if the array contains n elements then binary search requires log₂ n comparisons. This results in a big O Notation of O(log n) by omitting the base.

Hence, the Time Complexity for Binary Search is O(log n).

• Data Structures
• Java