Solution Approach

We use the standard binary search template with first_true_index to track our answer. The key insight is defining a feasible function that tells us whether the target could be at or before the current position.

Template Structure:

left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index if first_true_index != -1 and nums[first_true_index] == target else -1

Defining the Feasible Function:

The feasible function returns True when the target is at index mid or should be to its left. This depends on which half is sorted:

1. If left half is sorted (nums[0] <= nums[mid]):

   • Feasible if nums[0] <= target <= nums[mid] (target is in sorted left half)

2. If right half is sorted (nums[0] > nums[mid]):

   • Feasible if target is NOT in the sorted right half
   • That is, NOT (nums[mid] < target <= nums[n-1])

Why This Works:

When feasible returns True, we save the current mid as a potential answer and search left for an earlier occurrence. When feasible returns False, the target must be to the right.

After the loop, first_true_index holds the position where our feasible condition first became true. We then verify that nums[first_true_index] == target to confirm the target exists.

Time Complexity: O(log n) - we eliminate half of the search space in each iteration Space Complexity: O(1) - only using a constant amount of extra space for pointers

Example Walkthrough

Let's trace through the algorithm with array [4,5,6,7,0,1,2] searching for target = 0.

Initial State:

• Array: [4,5,6,7,0,1,2] (indices 0-6)
• left = 0, right = 6, first_true_index = -1, target = 0

Iteration 1:

• Calculate mid = (0 + 6) // 2 = 3
• nums[mid] = 7
• Check if left half is sorted: nums[0] = 4 <= nums[3] = 7 ✓
• Is target in sorted left half? Check if 4 <= 0 <= 7: No (0 < 4)
• Feasible = False → left = mid + 1 = 4

Iteration 2:

• left = 4, right = 6
• Calculate mid = (4 + 6) // 2 = 5
• nums[mid] = 1
• Check if left half is sorted: nums[0] = 4 <= nums[5] = 1? No
• Right half is sorted. Is target in sorted right half? 1 < 0 <= 2? No (0 < 1)
• Feasible = True → first_true_index = 5, right = mid - 1 = 4

Iteration 3:

• left = 4, right = 4
• Calculate mid = (4 + 4) // 2 = 4
• nums[mid] = 0
• Check if left half is sorted: nums[0] = 4 <= nums[4] = 0? No
• Right half is sorted. Is target in sorted right half? 0 < 0 <= 2? No (0 is not > 0)
• Feasible = True → first_true_index = 4, right = mid - 1 = 3

Iteration 4:

• left = 4, right = 3
• Loop condition left <= right is false, exit loop

Final Check:

• first_true_index = 4
• Does nums[4] == target? Yes, 0 == 0 ✓
• Return 4

The algorithm successfully finds the target at index 4, demonstrating the O(log n) efficiency with the standard binary search template.

Time and Space Complexity

Time Complexity: O(log n), where n is the length of the array nums. The algorithm uses the binary search template with while left <= right. In each iteration, the search space is reduced by half (either updating left = mid + 1 or right = mid - 1), which results in at most log₂(n) iterations.

Space Complexity: O(1). The algorithm only uses a constant amount of extra space for the variables n, left, right, mid, and first_true_index, regardless of the input size. No additional data structures or recursive calls are used.

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

Common Pitfalls

1. Using Wrong Binary Search Template Variant

The Pitfall: Using while left < right with right = mid instead of the standard template with first_true_index tracking. This variant can be confusing and error-prone.

Example of the Issue:

# Non-standard variant (harder to reason about)
while left < right:
    mid = (left + right) >> 1
    if condition:
        right = mid
    else:
        left = mid + 1
return left if nums[left] == target else -1

Solution: Use the standard binary search template with explicit answer tracking:

left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index if first_true_index != -1 and nums[first_true_index] == target else -1

2. Incorrect Boundary Comparison When Determining the Sorted Half

The Pitfall: Using strict inequality (nums[0] < nums[mid]) instead of nums[0] <= nums[mid] when determining which half is sorted.

Example of the Issue:

if nums[0] < nums[mid]:  # Wrong! Missing the equal case
    # Left half logic

Consider the array [3, 1] searching for target 1:

• With strict inequality: 3 < 3 is false, incorrectly assuming right half is sorted
• With correct comparison: 3 <= 3 is true, correctly identifying left half pattern

Solution: Always use <= to properly handle all cases:

if nums[0] <= nums[mid]:  # Correct
    # Left half is sorted

3. Off-by-One Errors in Feasible Function

The Pitfall: When checking if the target falls within a sorted range, using incorrect comparison operators.

Example of the Issue:

# Wrong comparison for right half
feasible = not (nums[mid] <= target <= nums[n - 1])  # Includes mid incorrectly

Solution: Use the correct comparisons:

# For left sorted half (target at or before mid):
feasible = nums[0] <= target <= nums[mid]

# For right sorted half (target NOT in right half):
feasible = not (nums[mid] < target <= nums[n - 1])  # Note: strictly < for mid

4. Forgetting to Validate first_true_index

The Pitfall: Not checking if first_true_index is still -1 (no valid position found) or if the element at that position equals the target.

Example of the Issue:

# Missing validation
return first_true_index  # Wrong! Might return -1 or wrong index

Solution: Always validate after the loop:

if first_true_index == -1:
    return -1
return first_true_index if nums[first_true_index] == target else -1