Problem

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].

Input: A sorted array, arrA[] and an key Output : Return index if element is found, else -1.

Examples

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Solution

A straightforward method is to perform a linear search. The time complexity of this approach is ( O(n) ). An alternative method is to use Binary Search.

Binary Search is based on the principle of divide and conquer, aiming to find an item in an ordered list recursively.

To search a sorted array, continually divide the search interval in half. Start with the whole array. If the search key is less than the middle item, reduce the interval to the lower half. Otherwise, reduce it to the upper half. Repeat until the value is found or the interval is empty.

To sum up: Binary search operates only on a pre-sorted list.

[2, 3, 5, 8, 10, 15, 22, 23]
 ^            ^           ^
low          mid         high
  • If the item at the midpoint is the target, return it.
  • If the item at the midpoint is greater than the target, move high below the midpoint:
[2, 3, 5, 8, 10, 15, 22, 23]
 ^        ^
low      high
  • If the item at the midpoint is less than the target, move low above the midpoint:
[2, 3, 5, 8, 10, 15, 22, 23]
                  ^       ^
                 low     high

Continue this process until the target is found. Binary search can be implemented both recursively and iteratively.

Pseudocode

BINARY_SEARCH(array, start, end, target)
  middle := (start + end) / 2
  if array[middle] = target
    return array[middle]
  else if array[middle] > target
    BINARY_SEARCH(array, start, middle - 1, target)
  else if array[middle] < target
    BINARY_SEARCH(array, middle + 1, end, target)

Examples

< Or <=?

Sometimes, we do low < high or low <= high, there is no hard and fast rule. But below can help:

  • If you are returning from inside the loop, use low <= high
  • If you are reducing the search space, use low < high and finally return a low

Method 1 - Recursive

public int search(int[] array, int key) {
    return binarySearchHelper(array, key, 0, array.length - 1);
}

private static int binarySearchHelper(int[] array, int key, int start, int end) {

    if (start < end) {
        int mid = start + (end - start) / 2;  // Compute mid point.
        if (key < array[mid]) {
            return binarySearchHelper(array, start, mid, key);

        } else if (key > array[mid]) {
            return binarySearchHelper(array, mid + 1, end, key);

        } else {
            return mid;  // Found it.
        }
    }
    return -(start + 1);  // Failed to find key
}

Method 2 - Iterative

public int search(int array[], int key) {
    int left, right, middle;
    left  = 0;
    right = array.length - 1;

    while (left <= right) {
        middle = ((left + right) / 2);

        if (key == array[middle]) { // first comparison
            return (middle);
        }

        if (key > array[middle]) { // second comparison
            left  = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return -1;
}

We can reduce the comparison further:

int BinarySearch(int A[], int key){
    int m, l = 0, r = A.length - 1;

    while( r - l > 1 ) {
        m = l + (r-l)/2;

        if( A[m] <= key )
            l = m;
        else
            r = m;
    }

    if( A[l] == key )
        return l;
    else
        return -1;
}

Time Complexity Analysis

Time Complexity

In Binary Search, with each iteration, we discard half the elements and continue searching with the remaining half until the target element is found or the search space is empty. In each iteration, the search space is halved. For instance, if the search space has ( n ) elements:

Iteration 1: ( n/2 = n/2^1 )

Iteration 2: ( (n/2)/2 = n/4 = n/2^2 )

Iteration 3: ( (n/4)/2 = n/8 = n/2^3 )

This process terminates when we have one element left in the array and assume the iteration number as k

Iteration k:  n/2^k = 1  => k =log2(n)

Time Complexity = log2(n) where n is the number of elements in the search space.

Runs in $O(log \cdot n)$ time.

Space Complexity

The space complexity of the binary search algorithm depends on its implementation (iterative or recursive).

  • In the iterative implementation, no extra auxiliary space is used, so the space complexity is O(1).
  • In the recursive implementation, each recursive call uses ($\log_2(n)$) stack space on average, so the space complexity is O(\log n).