Problem Description

You are given a sorted array of integers nums in ascending order and an integer target. Your task is to search for the target value in the array.

The function should:

• Return the index of target if it exists in the array
• Return -1 if target is not found in the array

Important constraint: Your algorithm must have O(log n) runtime complexity, which means you need to use binary search rather than a linear scan through the array.

For example:

• If nums = [1, 3, 5, 7, 9] and target = 5, the function should return 2 (since nums[2] = 5)
• If nums = [1, 3, 5, 7, 9] and target = 6, the function should return -1 (since 6 is not in the array)

The key insight is that since the array is sorted, you can eliminate half of the search space in each step by comparing the middle element with the target, leading to the required logarithmic time complexity.

Intuition

Since we need O(log n) complexity and the array is sorted, binary search is the natural choice. The sorted property allows us to make intelligent decisions about which half of the array to search next.

The key idea is to repeatedly divide the search space in half. At each step, we look at the middle element and ask: "Is our target in the left half or the right half?" We can answer this question by comparing the middle element with our target.

The specific implementation uses a slightly different variant of binary search. Instead of having three cases (found, go left, go right), it uses a two-way decision:

• If nums[mid] >= target, we include the middle element in our search space by setting r = mid
• If nums[mid] < target, we know the target must be to the right, so we exclude mid by setting l = mid + 1

This approach guarantees that if the target exists, it will eventually be at position l when the loop terminates (when l equals r). The reason this works is that we're essentially finding the leftmost position where nums[pos] >= target. If the element at that position equals our target, we've found it; otherwise, the target doesn't exist in the array.

The bit shift operation (l + r) >> 1 is just an efficient way to calculate the middle point, equivalent to (l + r) // 2, avoiding potential integer overflow issues in other languages.

Learn more about Binary Search patterns.

Solution Approach

We implement binary search with two pointers to find the target in the sorted array.

Step-by-step implementation:

1. Initialize boundaries: Set l = 0 (left boundary) and r = len(nums) - 1 (right boundary) to cover the entire array.

2. Binary search loop: Continue searching while l < r:

   • Calculate the middle position: mid = (l + r) >> 1 (equivalent to (l + r) // 2)
   • Compare nums[mid] with target:
     • If nums[mid] >= target: The target is either at mid or to its left, so we move the right boundary to mid by setting r = mid
     • If nums[mid] < target: The target must be to the right of mid, so we move the left boundary to mid + 1 by setting l = mid + 1

3. Check result: When the loop ends (when l == r), we have converged to a single position:

   • If nums[l] == target, we found the target and return l
   • Otherwise, the target doesn't exist in the array, so we return -1

Why this approach works:

The algorithm maintains an invariant that if the target exists in the array, it must be within the range [l, r]. By comparing with the middle element, we can safely eliminate half of the search space in each iteration.

The condition nums[mid] >= target ensures that we find the leftmost occurrence if there were duplicates (though this problem assumes unique elements). When l and r converge, l points to the smallest index where nums[index] >= target.

Time Complexity: O(log n) - We halve the search space in each iteration Space Complexity: O(1) - We only use a constant amount of extra space for the pointers

Example Walkthrough

Let's trace through the algorithm with nums = [1, 3, 5, 7, 9, 11] and target = 7.

Initial Setup:

• l = 0, r = 5 (array indices)
• Array: [1, 3, 5, 7, 9, 11]
• Looking for: 7

Iteration 1:

• l = 0, r = 5, so l < r (continue)
• Calculate mid = (0 + 5) >> 1 = 2
• Check nums[2] = 5
• Compare: 5 < 7, so target must be to the right
• Update: l = mid + 1 = 3
• New range: indices [3, 5] → values [7, 9, 11]

Iteration 2:

• l = 3, r = 5, so l < r (continue)
• Calculate mid = (3 + 5) >> 1 = 4
• Check nums[4] = 9
• Compare: 9 >= 7, so target is at mid or to its left
• Update: r = mid = 4
• New range: indices [3, 4] → values [7, 9]

Iteration 3:

• l = 3, r = 4, so l < r (continue)
• Calculate mid = (3 + 4) >> 1 = 3
• Check nums[3] = 7
• Compare: 7 >= 7, so target is at mid or to its left
• Update: r = mid = 3
• New range: index [3] → value [7]

Termination:

• l = 3, r = 3, so l == r (exit loop)
• Check: nums[3] = 7, which equals our target
• Return: 3

Example with target not found: Let's quickly see what happens with the same array but target = 6:

• After similar iterations, we converge to l = r = 3
• Check: nums[3] = 7, which is 7 ≠ 6
• Return: -1

The algorithm efficiently narrows down the search space by half in each iteration, examining only 3 elements out of 6 to find the target, demonstrating the logarithmic time complexity.

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the length of the array nums. This is because the algorithm uses binary search, which divides the search space in half with each iteration. In the worst case, the while loop runs log₂(n) times until l and r converge.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the variables l, r, and mid, regardless of the input size. No additional data structures are created that scale with the input.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Empty Array Handling

The current implementation fails when the input array is empty. Accessing nums[left] when nums = [] will throw an IndexError.

Solution: Add an early check for empty arrays:

def search(self, nums: List[int], target: int) -> int:
    if not nums:  # Handle empty array
        return -1
  
    left, right = 0, len(nums) - 1
    # ... rest of the code

2. Integer Overflow in Middle Calculation

While Python handles large integers gracefully, in other languages like Java or C++, calculating mid = (left + right) // 2 can cause integer overflow when left + right exceeds the maximum integer value.

Solution: Use the overflow-safe formula:

mid = left + (right - left) // 2
# Or keep the bit shift version which is also safe:
mid = left + ((right - left) >> 1)

3. Incorrect Loop Condition Leading to Infinite Loop

A common mistake is using while left <= right with the update logic right = mid, which can cause an infinite loop when left == right and nums[mid] >= target.

Solution: Either:

• Keep while left < right with right = mid (as in the current code)
• Or use while left <= right with right = mid - 1:

while left <= right:
    mid = (left + right) >> 1
    if nums[mid] == target:
        return mid
    elif nums[mid] > target:
        right = mid - 1  # Note: mid - 1, not mid
    else:
        left = mid + 1

4. Confusing Binary Search Variants

The given implementation finds the leftmost position where nums[index] >= target. If the problem requires finding any occurrence (not necessarily the leftmost), the logic becomes simpler but different.

Solution for finding any occurrence:

def search(self, nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
  
    while left <= right:
        mid = (left + right) >> 1
        if nums[mid] == target:
            return mid  # Return immediately when found
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
  
    return -1

5. Off-by-One Errors in Boundary Updates

Forgetting to use mid + 1 or mid - 1 appropriately can lead to missing elements or infinite loops. The rule of thumb:

• When moving left boundary past mid: left = mid + 1
• When keeping mid in search space: right = mid
• When excluding mid from search space: right = mid - 1