How to Do a Binary Search on a Sorted Array

Introduction

Consider an array of integers. We suppose the integers are sorted by their natural order. If we have a particular integer value, we want to search the array to see if it’s included. In this article, we will show an approach based on a “divide and conquer” strategy, called “binary search”.

Problem Example

Consider an array of integers from 1 to 5, sorted by their natural order.

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

Suppose we want to search the above integer set to find the value 4. Exploiting the fact the numbers are sorted we can proceed like this:

• We divide the array by two and take the resulting value as its middle position
• We evaluate the value corresponding to the middle position
• If it equals 4 the search is terminated and we have a match
• If it’s less than 4 then we go on searching only on the left half of the array
• If it’s greater than 4 then we go on searching only on the right half
• We repeat the above steps until we cannot divide further

We can implement the above steps in two equivalent ways: iteratively and recursively. We will show both these approaches in the next sections.

Binary Search in an Iterative Way

We can decline the generic description of the algorithm iteratively. While the first index the array is less or equal to the last one:

• We calculate the difference between the last and first index of the array and divide by 2
• We set the middle index of the array as the first index plus the previous calculation (it is necessary to calculate the right value of the middle index if the divide operation is made more than once)
• If the value corresponding to the middle index is equal to 4 we have a match and we stop the searching
• If 4 is less than it, then we set the second index as the middle one minus 1 and repeat the calculation of the middle index for the left half
• If 4 is greater than it, then we set the first index as the middle one plus 1 and repeat the calculation of the middle index for the right half

We can implement what is said above by Java code:

@Test
public void binarySearchIterativeTest() throws Exception {
    int[] sortedSet = { 1, 2, 3, 4, 5 };
    int keyValue = 4;
    int i = 0, j = sortedSet.length - 1;
    int searchResult = -1;
    int middle = -1;
    while (i <= j) {
        middle = i + (j - i) / 2;
        if (keyValue == sortedSet[middle]) {
            searchResult = sortedSet[middle];
            break;
        }
        if (keyValue < sortedSet[middle]) {
            j = middle - 1;
        } else if (keyValue > sortedSet[middle]) {
            i = middle + 1;
        }
    }
    assertEquals(4, searchResult);
    System.out.println(searchResult);
}

Performance Considerations

The time complexity of the above algorithm is O(log n).

Binary Search in a Recursive Way

We can re-write the algorithm shown in the previous section recursively. The logic is the same, but we exploit a recursive function to implement the repeating part:

private int binarySearchRecursive(int[] sortedSet, int i, int j, int keyValue) throws Exception {
    if (i <= j) {
        int middle = i + (j - i) / 2;
        if (keyValue == sortedSet[middle]) {
            return sortedSet[middle];
        }
        if (keyValue < sortedSet[middle]) {
            j = middle - 1;
        } else if (keyValue > sortedSet[middle]) {
            i = middle + 1;
        }
        return binarySearchRecursive(sortedSet, i, j, keyValue);
    }
    return -1;
}

@Test
public void binarySearchRecursiveTest() throws Exception {
    int[] sortedSet = { 1, 2, 3, 4, 5 };
    int i = 0, j = sortedSet.length - 1;
    int keyValue = 4;
    int result = binarySearchRecursive(sortedSet, i, j, keyValue);
    assertEquals(4, result);
    System.out.println(result);
}

Performance Considerations

The time complexity of the above algorithm is O(log n).

Conclusion

In this article, we have seen an iterative and recursive approach to perform a binary search on a sorted array of integers. The example code is available on GitHub.