Binary Search on Sorted Array

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.

OR

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

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

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/wUDX4QKzbug" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Linear Search

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

Method 2 - Recursive 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.

Approach

1. Start with two pointers (low and high), representing the start and end of the array.
2. Calculate the middle index: mid = low + (high - low) // 2.
3. Compare the middle element (arr[mid]) with the target (x):
   • If arr[mid] == x, return mid (element found).
   • If arr[mid] > x, search the left half (high = mid - 1).
   • If arr[mid] < x, search the right half (low = mid + 1).
4. Repeat until low > high (element not found).

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

Code

Java

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums, target, 0, nums.length - 1);
    }

    private int binarySearch(int[] nums, int target, int left, int right) {
        // Base condition: if left exceeds right, the search space is exhausted
        if (left > right) {
            return -1; // Target not found
        }

        int mid = left + (right - left) / 2; // Calculate the midpoint safely to avoid overflow

        // Check if the midpoint element matches the target
        if (nums[mid] == target) {
            return mid; // Target found
        } else if (nums[mid] > target) {
            return binarySearch(nums, target, left, mid - 1); // Search in the left subarray
        } else {
            return binarySearch(nums, target, mid + 1, right); // Search in the right subarray
        }
    }
}

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        return self.binary_search(nums, target, 0, len(nums) - 1)
    
    def binary_search(self, nums: List[int], target: int, left: int, right: int) -> int:
        # Base condition: if left exceeds right, the search space is exhausted
        if left > right:
            return -1  # Target not found

        mid = left + (right - left) // 2  # Calculate the midpoint safely to avoid overflow

        # Check if the midpoint element matches the target
        if nums[mid] == target:
            return mid  # Target found
        elif nums[mid] > target:
            return self.binary_search(nums, target, left, mid - 1)  # Search in the left subarray
        else:
            return self.binary_search(nums, target, mid + 1, right)  # Search in the right subarray

Method 3 - Iterative Binary search

Pseudocode

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;
}

Code

Java

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2; // Calculate the middle index
            if (nums[mid] == target) {
                return mid; // Element found
            } else if (nums[mid] > target) {
                right = mid - 1; // Search in the left half
            } else {
                left = mid + 1; // Search in the right half
            }
        }

        return -1; // Element not found in the array
    }
}

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2  # Calculate the middle index
            if nums[mid] == target:
                return mid  # Element found
            elif nums[mid] > target:
                right = mid - 1  # Search in the left half
            else:
                left = mid + 1  # Search in the right half

        return -1  # Element not found in the array

public int search(int array[], int target) {
    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;
}

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).