Binary Search

Given a sorted array of integers and a target value, return the index of the target if found, or -1 if not present.

Language Selection

Choose your preferred programming language

Showing: Python

Binary Search

Problem Statement

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.

Example 3:

Input: nums = [5], target = 5
Output: 0
Explanation: 5 exists in nums and its index is 0.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 < nums[i], target < 10^4
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Approach 1: Iterative Binary Search (Optimal)

Algorithm Explanation

Binary search works by repeatedly dividing the search interval in half. We maintain two pointers, left and right, that define the current search range. At each step we compute the middle index and compare the middle element with the target:

  1. If nums[mid] == target, we found it – return mid.
  2. If nums[mid] < target, the target must be in the right half, so set left = mid + 1.
  3. If nums[mid] > target, the target must be in the left half, so set right = mid - 1.
  4. If left > right, the target is not in the array – return -1.

Steps:

  1. Initialize left = 0 and right = len(nums) - 1
  2. While left <= right:
    • Compute mid = left + (right - left) / 2 (avoids integer overflow)
    • Compare nums[mid] with target and adjust pointers
  3. Return -1 if not found

Implementation

Python:

def search(nums, target):
    """
    Iterative binary search on a sorted array.
    Time: O(log n)
    Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Java:

class Solution {
    /**
     * Iterative binary search on a sorted array.
     * Time: O(log n)
     * Space: O(1)
     */
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

Go:

// search performs iterative binary search on a sorted array.
// Time: O(log n), Space: O(1)
func search(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        mid := left + (right-left)/2

        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

JavaScript:

/**
 * Iterative binary search on a sorted array.
 * Time: O(log n)
 * Space: O(1)
 */
function search(nums, target) {
    let left = 0, right = nums.length - 1;

    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

C#:

public class Solution {
    /// <summary>
    /// Iterative binary search on a sorted array.
    /// Time: O(log n)
    /// Space: O(1)
    /// </summary>
    public int Search(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

Complexity Analysis

  • Time Complexity: O(log n) – the search space is halved at each step.
  • Space Complexity: O(1) – only a constant number of variables are used.

Algorithm Explanation

The recursive approach mirrors the iterative one but uses function call recursion instead of a loop. At each recursive call we compute the midpoint, compare, and recurse into the appropriate half.

Steps:

  1. Define a helper function binarySearch(nums, target, left, right)
  2. Base case: if left > right, return -1
  3. Compute mid and compare nums[mid] with target
  4. Recurse into the left or right half as needed

Implementation

Python:

def search_recursive(nums, target):
    """
    Recursive binary search on a sorted array.
    Time: O(log n)
    Space: O(log n) due to recursion stack
    """
    def helper(left, right):
        if left > right:
            return -1

        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            return helper(mid + 1, right)
        else:
            return helper(left, mid - 1)

    return helper(0, len(nums) - 1)

Java:

class Solution {
    /**
     * Recursive binary search on a sorted array.
     * Time: O(log n)
     * Space: O(log n) due to recursion stack
     */
    public int searchRecursive(int[] nums, int target) {
        return helper(nums, target, 0, nums.length - 1);
    }

    private int helper(int[] nums, int target, int left, int right) {
        if (left > right) {
            return -1;
        }

        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            return helper(nums, target, mid + 1, right);
        } else {
            return helper(nums, target, left, mid - 1);
        }
    }
}

Go:

// searchRecursive performs recursive binary search on a sorted array.
// Time: O(log n), Space: O(log n) due to recursion stack
func searchRecursive(nums []int, target int) int {
    return helper(nums, target, 0, len(nums)-1)
}

func helper(nums []int, target, left, right int) int {
    if left > right {
        return -1
    }

    mid := left + (right-left)/2

    if nums[mid] == target {
        return mid
    } else if nums[mid] < target {
        return helper(nums, target, mid+1, right)
    } else {
        return helper(nums, target, left, mid-1)
    }
}

JavaScript:

/**
 * Recursive binary search on a sorted array.
 * Time: O(log n)
 * Space: O(log n) due to recursion stack
 */
function searchRecursive(nums, target) {
    function helper(left, right) {
        if (left > right) {
            return -1;
        }

        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            return helper(mid + 1, right);
        } else {
            return helper(left, mid - 1);
        }
    }

    return helper(0, nums.length - 1);
}

C#:

public class Solution {
    /// <summary>
    /// Recursive binary search on a sorted array.
    /// Time: O(log n)
    /// Space: O(log n) due to recursion stack
    /// </summary>
    public int SearchRecursive(int[] nums, int target) {
        return Helper(nums, target, 0, nums.Length - 1);
    }

    private int Helper(int[] nums, int target, int left, int right) {
        if (left > right) {
            return -1;
        }

        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            return Helper(nums, target, mid + 1, right);
        } else {
            return Helper(nums, target, left, mid - 1);
        }
    }
}

Complexity Analysis

  • Time Complexity: O(log n) – the search space is halved at each recursive call.
  • Space Complexity: O(log n) – recursion stack depth is at most log n.

Key Insights

  1. Sorted Array Prerequisite: Binary search requires the input array to be sorted. Always confirm this before applying the technique.
  2. Overflow-Safe Midpoint: Use mid = left + (right - left) / 2 instead of (left + right) / 2 to prevent integer overflow in languages with fixed-size integers.
  3. Loop Invariant: The target, if present, always lies within [left, right]. This invariant guides the pointer updates.
  4. Halving the Search Space: Each comparison eliminates half the remaining elements, yielding logarithmic time complexity.
  5. Iterative vs Recursive: The iterative version uses O(1) space while the recursive version uses O(log n) space for the call stack. In practice, the iterative version is preferred.

Edge Cases

  1. Single Element Array: nums = [5], target = 5 – target is the only element.
  2. Target Not Found: nums = [1,3,5], target = 4 – target does not exist in the array.
  3. Target at Start: nums = [1,2,3,4,5], target = 1 – target is the first element.
  4. Target at End: nums = [1,2,3,4,5], target = 5 – target is the last element.
  5. Two Elements: nums = [1,3], target = 3 – small array with target at end.
  6. Negative Numbers: nums = [-10,-5,0,3,7], target = -5 – array contains negative values.

Test Cases

def test_search():
    # Test case 1: Target in the middle
    assert search([-1, 0, 3, 5, 9, 12], 9) == 4

    # Test case 2: Target not found
    assert search([-1, 0, 3, 5, 9, 12], 2) == -1

    # Test case 3: Single element found
    assert search([5], 5) == 0

    # Test case 4: Single element not found
    assert search([5], 2) == -1

    # Test case 5: Target at the beginning
    assert search([1, 2, 3, 4, 5], 1) == 0

    # Test case 6: Target at the end
    assert search([1, 2, 3, 4, 5], 5) == 4

    # Test case 7: Negative numbers
    assert search([-10, -5, 0, 3, 7], -5) == 1

    # Test case 8: Two elements
    assert search([1, 3], 3) == 1

    # Test recursive version
    assert search_recursive([-1, 0, 3, 5, 9, 12], 9) == 4
    assert search_recursive([-1, 0, 3, 5, 9, 12], 2) == -1
    assert search_recursive([5], 5) == 0

    print("All tests passed!")

test_search()

Common Mistakes

  1. Integer Overflow in Midpoint: Computing (left + right) / 2 can overflow in Java/C++/C#. Always use left + (right - left) / 2.
  2. Wrong Loop Condition: Using left < right instead of left <= right causes missing the case where left == right (the target sits at the single remaining position).
  3. Incorrect Pointer Update: Setting right = mid or left = mid instead of mid - 1 / mid + 1 can cause infinite loops because the search space never shrinks.
  4. Off-by-One Errors: Forgetting that the search is inclusive on both ends [left, right] leads to skipping elements or re-checking elements.
  5. Assuming Sorted Input: Applying binary search on an unsorted array produces incorrect results. Always verify the array is sorted.

Interview Tips

  1. Clarify Constraints: Ask whether the array is sorted and whether elements are unique.
  2. Start Simple: Write the iterative version first – it is cleaner and uses O(1) space.
  3. Explain the Invariant: Articulate that the target always lies within [left, right] at each iteration.
  4. Mention Overflow: Proactively mention the overflow-safe midpoint calculation.
  5. Discuss Variants: Be ready for follow-ups such as finding the first/last occurrence, or the insertion position (LeetCode #35).