Binary Search

Binary Search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. It works only on a sorted set of elements. To use binary search on a collection, the collection must first be sorted.

When the binary search is used to perform operations on a sorted set, the number of iterations can always be reduced on the basis of the value that is being searched. You can see in the below snapshot of finding the mid element. The analogy of binary search is to use the information that the array is sorted and reduce the time complexity to O(log n).

 

Advantages

  • binary search algorithm is a fairly simple search algorithm to implement. 
  • It is a significant improvement over linear search and performs almost the same in comparison to some of the harder to implement search algorithms.
  • The binary search algorithm breaks the list down in half on every iteration, rather than sequentially combing through the list. On large lists, this method can be really useful.

Note that the array has to be sorted.

Binary Search in a iterative way

Time: O(log n)
Space: O(log n) or O(1)

public int search(int array[], int searchElement, int lowIndex, int highIndex) {

    // Repeat until the pointers low and high meet each other
    while (lowIndex <= highIndex) {

        // get index of mid element
        int midIndex = lowIndex + (highIndex - lowIndex) / 2;

        int midValue = array[midIndex];

        // if element to be searched is the mid element
        if (midValue == searchElement) {
            return midIndex;
        }

        // if element is less than mid element
        // search only the left side of mid
        if (midValue < searchElement) {
            lowIndex = midIndex + 1;

            // if element is greater than mid element
            // search only the right side of mid
        } else {
            highIndex = midIndex - 1;
        }
    }

    return -1;
}

 

Notice how the middle index is generated (int mid = low + ((high – low) / 2). This to accommodate for extremely large arrays. If the middle index is generated simply by getting the middle index (int mid = (low + high) / 2), an overflow may occur for an array containing 230 or more elements as the sum of low + high could easily exceed the maximum positive int value.

Binary Search in a recursive way
Time: O(log n)
Space: O(log n)

public int search(int array[], int searchElement, int lowIndex, int highIndex) {
    if (highIndex >= lowIndex) {
        int midIndex = lowIndex + (highIndex - lowIndex) / 2;

        int midValue = array[midIndex];

        // check if mid element is searched element
        if (midValue == searchElement) {
            return midIndex;
        }

        // Search the left half of mid
        if (midValue > searchElement) {
            return searchWithRecursion(array, searchElement, lowIndex, midIndex - 1);
        }

        // Search the right half of mid
        return searchWithRecursion(array, searchElement, midIndex + 1, highIndex);
    }

    return -1;
}

Tests

CustomBinarySearch bs = new CustomBinarySearch();

int[] numbers = {1, 4, 6, 45, 367};

Arrays.sort(numbers);

int searchNumber = 6;

int searchNumberIndex = bs.search(numbers, searchNumber, 0, numbers.length - 1);

System.out.println("searchNumber: " + searchNumber + ", searchNumberIndex: " + searchNumberIndex);

searchNumberIndex = bs.searchWithRecursion(numbers, searchNumber, 0, numbers.length - 1);

System.out.println("searchNumber: " + searchNumber + ", searchNumberIndex: " + searchNumberIndex);

 

Is it better to do a recursive binary search or an iterative binary search?

The recursive version of Binary Search has a space complexity of O(log N), but the iterative version has a space complexity of O(log N) (1). As a result, while the recursive version is simple to build, the iterative form is more efficient.

  1. Recursion can be slower due to the overhead of maintaining a stack and usually takes up more memory
  2. Recursion is not stack-friendly. It may cause StackOverflowException when processing big data sets
  3. Recursion adds clarity to the code as it makes it shorter in comparison to the iterative approach

Ideally, a binary search will perform less number of comparisons in contrast to a linear search for large values of n. For smaller values of n, the linear search could perform better than a binary search.

One should know that this analysis is theoretical and might vary depending on the context.

Using binary search in java

Binary search with java array

int index = Arrays.binarySearch(sortedArray, key);

Binary search with java collection

int index = Collections.binarySearch(sortedList, key);

 

Source code on Github

 




Subscribe To Our Newsletter
You will receive our latest post and tutorial.
Thank you for subscribing!

required
required


Leave a Reply

Your email address will not be published.