Binary Search in Java

Introduction

From picking your cherished pair of jeans from your wardrobe to choosing the next movie to watch with your partner, human life is filled with searching for things.

While in day-to-day life, humans usually search between a few, if not a dozen, items. Computers have to deal with searching through data of comparatively massive amounts in terms of their size and quantity.

This warrants a computer's need to have an efficient method to search inside its arrays and collections as efficiently as possible.

Being able to find information amidst a collection is one of the most basic functional points of an application.

Binary Search

Binary Search (sometimes known as Logarithmic Search) is a widely popular algorithm to search a sorted array for the position of a given element.

It works on a divide and conquer basis by comparing the target element with the middle element of the array. In case a match is found - its position is returned, otherwise if the target element is smaller than the middle element, it can't be on the right side of the middle element.

Therefore, the right half of the array (including middle element) is discarded and the search is continued on the left half using the same approach.

Similarly in case the target element is larger than the middle element, it cannot be on a place preceding the middle of the array. Therefore, the left half of the array is discarded and the search is continued on the right half.

This is repeated until a match is found.

We can make this assumption simply because we know that the array is sorted beforehand. If it weren't sorted, we couldn't implement Binary Search.

Here's a visual representation of how Binary Search works:

Implementation

Since we have a repeating step (checking for the middle element and discarding one half of the array), we can implement the algorithm using two approaches - an iterative approach and a recursive approach.

As usual, there's no clear winner between these two and you can choose to use any one of these based on your personal preference.

Iterative

Let's start off with the iterative implementation:

public static int iterativeSearch(int[] arrayToSearch, int element) {
    int lowIndex = 0;
    int highIndex = arrayToSearch.length-1;

    // Holds the position in array for given element
    // Initial negative integer set to be returned if no match was found on array
    int elementPos = -1;

    // If lowIndex less than highIndex, there's still elements in the array
    while (lowIndex <= highIndex) {
        int midIndex = (lowIndex + highIndex) / 2;
        if (element == arrayToSearch[midIndex]) {
            elementPos = midIndex;
            break;
        } else if (element < arrayToSearch[midIndex]) {
            highIndex = midIndex-1;
        } else if (element > arrayToSearch[midIndex]) {
            lowIndex = midIndex+1;
        }
    }
    return elementPos;
}

We need to keep track of the lowIndex (the first index) and the highIndex (last index) to get the arithmetic middle for the array. The elementPos by default is -1 which signifies that the element hasn't been found.

If it hasn't, we simply return this position. If it has, we adjust the elementPos to reflect the location in the array.

Then, through a while loop, we check if the middle element is the one we're searching for. If not, we adjust the lowIndex and highIndex to disregard the half of the array that the target element isn't in.

Recursive

The recursive implementation is fairly straightforward too, but we simply call the method recursively until the element has been found:

public static int recursiveSearch(int[] arrayToSearch, int element) {
    return recursiveSearch(arrayToSearch, element, 0, arrayToSearch.length-1);
}

private static int recursiveSearch(int[] arrayToSearch, int element, int lowIndex, int highIndex) {
    // If lowIndex surpasses highIndex, the element has not been found
    if (lowIndex > highIndex) return -1;

    // Default assumption is that the element is not found
    int elementPos = -1;

    int midIndex = (lowIndex + highIndex) / 2;

    if (element == arrayToSearch[midIndex]) {
        elementPos = midIndex;
    } else if (element < arrayToSearch[midIndex]) {
        recursiveSearch(arrayToSearch, element, lowIndex, midIndex-1);
    } else if (element > arrayToSearch[midIndex]) {
        recursiveSearch(arrayToSearch, element, midIndex+1, highIndex);
    }
    return elementPos;
}

Benchmarking Binary Search

To analyze how efficiently Binary Search algorithm works with given integer datasets, let's run the code against integer arrays of varied sizes and observe the runtimes it takes for a binary search to find a given number, expressed in nanoseconds:

Big-O Analysis

On each of its search iterations, Binary Search halves the set of items it searches. This leads the Binary Search algorithm to retain a worst case efficiency of logarithmic time. In Big-O Notation terms, an O(log n) complexity.

More so, in case the target element was found in the very middle of the array on the first go, the operation would have completed in linear time. From that we can deduce that Binary Search has a best case efficiency of O(1).

Therefore, conclusively Binary Search algorithm has an average performance of O(log n) .

It's also critical to mention that although the algorithm is greatly effective for searching arrays, its logic requires the searched array to be sorted beforehand.

In case you plan to use the algorithm on an unsorted array, you would have to sort it first - causing an increased complexity. In this case even a typical linear search would typically dominate Binary Search with its O(n) complexity.

Conclusion

Since first being mentioned way back in 1946 by John Mauchly, Binary Search has been preserved to this date as an easy-to-understand and highly efficient algorithm for searching sorted arrays for positions of its target elements.

It works on a divide and conquer basis by comparing the target element with the middle element of the array. In this article, we've implemented both the Iterative and Recursive approaches and benchmarked the algorithm with three different sets of integers.

Additionally, we've done a quick Big-O Analysis to prove the efficiency of this basic, yet effective search algorithm.