704. Binary Search - Explanation

Description

You are given an array of distinct integers nums, sorted in ascending order, and an integer target.

Implement a function to search for target within nums. If it exists, then return its index, otherwise, return -1.

Your solution must run in $O(log n)$ time.

Example 1:

Input: nums = [-1,0,2,4,6,8], target = 4

Output: 3

Example 2:

Input: nums = [-1,0,2,4,6,8], target = 3

Output: -1

Constraints:

1 <= nums.length <= 10000.
-10000 < nums[i], target < 10000
All the integers in nums are unique.

Recommended Time & Space Complexity

You should aim for a solution with O(logn) time and O(1) space, where n is the size of the input array.

Hint 1

Can you find an algorithm that is useful when the array is sorted? Maybe other than linear seacrh.

Hint 2

The problem name is the name of the algorithm that we can use. We need to find a target value and if it does not exist in the array return -1. We have l and r as the boundaries of the segment of the array in which we are searching. Try building conditions to eliminate half of the search segment at each step. Maybe sorted nature of the array can be helpful.

Hint 3

We compare the target value with the mid of the segment. For example, consider the array [1, 2, 3, 4, 5] and target = 4. The mid value is 3, thus, on the next iteration we search to the right of mid. The remaining segment is [4,5]. Why?

Hint 4

Because the array is sorted, all elements to the left of mid (including 3) are guaranteed to be smaller than the target. Therefore, we can safely eliminate that half of the array from consideration, narrowing the search to the right half and repeat this search until we find the target.

Company Tags

1. Recursive Binary Search

Intuition

Binary search works by repeatedly cutting the search space in half.
Instead of scanning the entire array, we check the middle element:

If it’s the target → return the index.
If the target is larger → search only in the right half.
If the target is smaller → search only in the left half.

The recursive version simply expresses this idea as a function that keeps calling itself on the appropriate half until the target is found or the range becomes invalid.

Algorithm

Define a recursive function that takes the current search range [l, r].
If l > r, the range is empty → return -1.
Compute the middle index m = (l + r) // 2.
Compare nums[m] with target:
- If equal → return m.
- If nums[m] < target → recursively search [m + 1, r].
- If nums[m] > target → recursively search [l, m - 1].
Start the recursion with the full range [0, n - 1].
Return the final result.

class Solution:
    def binary_search(self, l: int, r: int, nums: List[int], target: int) -> int:
        if l > r:
            return -1
        m = l + (r - l) // 2

        if nums[m] == target:
            return m
        if nums[m] < target:
            return self.binary_search(m + 1, r, nums, target)
        return self.binary_search(l, m - 1, nums, target)

    def search(self, nums: List[int], target: int) -> int:
        return self.binary_search(0, len(nums) - 1, nums, target)

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$

2. Iterative Binary Search

Intuition

Binary search checks the middle element of a sorted array and decides which half to discard.
Instead of using recursion, the iterative approach keeps shrinking the search range using a loop.
We adjust the left and right pointers until we either find the target or the pointers cross, meaning the target isn’t present.

Algorithm

Initialize two pointers:
- l = 0 (start of array)
- r = len(nums) - 1 (end of array)
While l <= r:
- Compute m = l + (r - l) // 2 (safe midpoint).
- If nums[m] == target, return m.
- If nums[m] < target, move search to the right half: update l = m + 1.
- If nums[m] > target, move search to the left half: update r = m - 1.
If the loop ends without finding the target, return -1.

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

        while l <= r:
            # (l + r) // 2 can lead to overflow
            m = l + ((r - l) // 2)

            if nums[m] > target:
                r = m - 1
            elif nums[m] < target:
                l = m + 1
            else:
                return m
        return -1

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

3. Upper Bound

Intuition

Upper bound binary search finds the first index where a value greater than the target appears.
Once we know that position, the actual target—if it exists—must be right before it.
So instead of directly searching for the target, we search for the boundary where values stop being ≤ target.
Then we simply check whether the element just before that boundary is the target.

Algorithm

Set l = 0 and r = len(nums) (right is one past the last index).
While l < r:
- Compute midpoint m.
- If nums[m] > target, shrink the right side → r = m.
- Otherwise (nums[m] <= target), shrink the left side → l = m + 1.
After the loop:
- l is the upper bound: first index where nums[l] > target.
- So the potential location of the target is l - 1.
If l > 0 and nums[l - 1] == target, return l - 1.
Otherwise, return -1 (target not found).

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

        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] > target:
                r = m
            elif nums[m] <= target:
                l = m + 1
        return l - 1 if (l and nums[l - 1] == target) else -1

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. Lower Bound

Intuition

Lower bound binary search finds the first index where a value is greater than or equal to the target.
This means if the target exists in the array, this lower-bound index will point exactly to its first occurrence.
So instead of directly searching for equality, we search for the leftmost position where the target could appear, then verify it.

This approach is especially useful for sorted arrays because it avoids overshooting and naturally handles duplicates.

Algorithm

Initialize:
- l = 0
- r = len(nums) (right is one past the last index).
While l < r:
- Compute midpoint m.
- If nums[m] >= target, shrink the search to the left half → r = m.
- Otherwise (nums[m] < target), search in the right half → l = m + 1.
After the loop:
- l is the lower bound: first index where value ≥ target.
If l is within bounds and nums[l] == target, return l.
Otherwise, return -1 (the target is not in the array).

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

        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] >= target:
                r = m
            elif nums[m] < target:
                l = m + 1
        return l if (l < len(nums) and nums[l] == target) else -1

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

5. Built-In Function

import bisect
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        index = bisect.bisect_left(nums, target)
        return index if index < len(nums) and nums[index] == target else -1

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$