Implement Binary Search in Java

Binary search is an efficient searching algorithm that works by dividing a sorted array into two parts and repeatedly searching in the part where the target element can possibly be found. It works on the principle of divide and conquer and has a time complexity of O(log n).

In this blog, we will discuss the implementation of binary search in Java.

Binary Search in Java:

Lets jump to the code directly:

public class BinarySearch {
    public static final int NOT_FOUND = -1;
    /*
     * Performs the standard binary search using two comparison per level.
     * @return index where item is found, or NOT_FOUND
     */
    public static int binarySearch(Comparable[] a, Comparable x) {
        int low = 0;
        int high = a.length - 1;
        int mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (a[mid].compareTo(x) < 0) 
              low = mid + 1;
            else if (a[mid].compareTo(x) > 0) 
              high = mid - 1;
            else 
              return mid;
        }
        return NOT_FOUND;
    }
    // Test program
    public static void main(String[] args) {
        int SIZE = 8;
        Comparable[] a = new Integer[SIZE];
        for (int i = 0; i < SIZE; i++) 
          a[i] = new Integer(i * 2);
        for (int i = 0; i < SIZE; i++) 
          System.out.println("Found " + i + " at " + binarySearch(a, new Integer(i)));
    }
}

Above program will give output as below:

Now, lets see what we did above:

Above Java code implements a recursive binary search algorithm to find the index of an element x in a sorted array a. Here is a step-by-step breakdown of how the code works:

The above code is an implementation of the binary search algorithm in Java. Here's how it works:

The binarySearch method takes two arguments - an array a of Comparable objects and a Comparable object x that we want to search for. It returns the index of the element in the array that matches x, or -1 if the element is not found.

The implementation is based on a while loop that runs until the element is found or until the search space has been exhausted. At each iteration of the loop, the algorithm checks the middle element of the remaining search space (defined by the low and high indices) and compares it with x.

If the middle element is less than x, the algorithm sets the new search space to the upper half of the current search space by updating low to mid + 1. If the middle element is greater than x, the algorithm sets the new search space to the lower half of the current search space by updating high to mid - 1. If the middle element is equal to x, the algorithm returns the index of the middle element.

If the loop completes without finding the element, the method returns -1 to indicate that the element was not found.

The main method is a test program that creates an array of Integer objects and searches for each value in the array using the binarySearch method. The output of the program is a sequence of lines that indicate the index at which each value was found in the array (or -1 if the value was not found).