Introduction:

In this quick tutorial, we’ll learn to perform a binary search in a sorted array. We’ll also write our own algorithmic implementation in Java. Later, we’ll discuss the binarySearch() method available in the Java library.

Problem Definition:

Let’s say we have a sorted array a[]:

int[] a = {1, 2, 3, 4, 5, 6};

And we want to search for a given element x in a[]. One approach of searching is to traverse through all the elements in our array and look for x in it. However, this approach doesn’t take an advantage of the fact that we have a sorted array.

We as developers always ask: ‘Can we do better?’

The answer here is yes. We’ll use the binary search algorithm to do so.

Binary Search:

Binary search is a decrease-and-conquer algorithm i.e. it reduces the problem domain to half in each iteration till we have it solved. The algorithm has the following steps:

1. Set low = 0, high = n-1
2. Finding the middle element in the array
3. If the middle element == x then return the current index, Or
4. If the x > middle element, then set low = mid + 1 (As it means x exists in the right half)
5. If x < middle element, set high = mid – 1 (As it means x exists in the left half)
6. Repeat starting from step 2 till low <= high holds true

Let’s implement it in Java:

int binarySearch(int[] a, int n, int x) {
    int low = 0, high = n-1;
    while(low <= high) {
        int mid = low + (high-low)/2;
        if(a[mid] == x)
            return mid;
        else if(x > a[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
    
    //element x not found
    return -1;
}

Clearly, in each iteration, we’re making a decision to search either in the left half or the right half of the remaining search space till we find the element. In case we still can’t find it, it simply means no such element exists. In that case, we’re returning -1.

Please note that we’ll have an unpredictable output if the array is unsorted.

Recursive Implementation:

Implementing binary search algorithm recursively is also pretty straightforward. So, our recursive algorithm implementation in Java would look like:

int binarySearch(int a[], int low, int high, int x) {
    
    if(low > high)
        return -1;
    int mid = low + (high - low)/2;
    if(a[mid] == x)
        return mid;
    else if(x < a[mid])
        return binarySearch(a, low, mid - 1, x);
    else
      return binarySearch(a, mid + 1, high, x);

}

Our recursive implementation accepts low and high as well as the part of its method arguments. To search for x=5, we’ll invoke this method as:

int index = binarySearch(a, 0, a.length - 1, 5);

Arrays.binarySearch():

Having looked at how to implement a binary search algorithm, let’s discuss the helper method available in our java.util.Arrays class in Java:

//x being the element we're looking for
int index = Arrays.binarySearch(a, x);

This method returns the index of the searched element if it exists in the sorted array. In case no such element exists, this method returns -(insertion point + 1) as an output. The insertion point is the index at which the key would exist in the array if it would have been present.

So, for example:

int[] a = {1, 2, 3, 4, 6, 7};

int indexOf4 = Arrays.binarySearch(a, 4); // indexOf4 = 3
int indexOf5 = Arrays.binarySearch(a, 5); // indexOf5 = -5

Collections.binarySearch():

Similar to Arrays.binarySearch(), we also have a method binarySearch() in our Collections class in Java. It helps us perform a binary search on some form of a Collection like an ArrayList or a LinkedList:

List<Integer> list = new ArrayList();
list.add(1);
list.add(2);
list.add(4);

int indexOf2 = Collections.binarySearch(list, 2); // indexOf2 = 1

Conclusion:

In this tutorial, we looked at the iterative as well as the recursive solution to implement the binary search algorithm in Java. We also discussed the Arrays.binarySearch() and Collections.binarySearch() utilities available in our Java library.