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.

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