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)

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.

Pattern Learn more about Binary Search patterns.

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

Step-by-step implementation:

1. Initialize boundaries: Set left = 0 and right = len(nums) - 1 to cover the entire array, and set first_true_index = -1 to record the best candidate found so far.

2. Binary search loop: Continue searching while left <= right:

   • Calculate the middle position: mid = (left + right) // 2
   • Compare nums[mid] with target:
     • If nums[mid] >= target: mid is a candidate, so we record first_true_index = mid and keep looking to its left by setting right = mid - 1
     • If nums[mid] < target: The target must be to the right of mid, so we set left = mid + 1

3. Check result: When the loop ends (when left > right), first_true_index holds the smallest index where nums[index] >= target, or -1 if every element is smaller than target:

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

Why this approach works:

The array is split into a prefix where nums[index] < target and a suffix where nums[index] >= target. Each comparison tells us which side of this boundary mid is on, so we can safely eliminate half of the search space in each iteration while keeping the best candidate in first_true_index.

The condition nums[mid] >= target finds the leftmost index with a value at least target. If the target exists, it is exactly at that index (and this would be its leftmost occurrence if there were duplicates, though this problem has unique elements).

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