Binary Search in Java with Example

It is an algorithm that searches for an element in a sorted array, and it follows a 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:

• Compare X with the middle element
• If X matches with middle element, return the index of element
• Else, if X is greater than the mid-element, then X can only lie in the right half subarray after the mid-element. So, repeat for right half
• Else (X is smaller), repeat for left half

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
   }

}