Time Complexity Analysis: The time complexity of this approach is O(n), where n is the number of elements in nums. In the worst-case scenario (target is at the end or not present), the algorithm must visit every element.

Why it fails: While this approach yields the correct result, the problem description explicitly requires an O(log n) runtime complexity. An O(n) solution is exponentially slower than O(log n) for large inputs. In a rigorous interview setting or against strict time limits, the brute force approach is considered incorrect because it fails to utilize the critical property that nums is sorted.

Core Insight for Binary Search

The key intuition behind the optimal solution lies in the sorted order of the input array. In an unsorted array, checking an element at index i gives us no information about the location of the target relative to i—the target could be anywhere. However, in a sorted array, comparing the target to a value at the middle index mid provides significant information:

1. If nums[mid] == target, we have found the element.
2. If nums[mid] > target, because the array is sorted ascendingly, all elements to the right of mid (indices mid + 1 to n - 1) must also be greater than target. Therefore, the target effectively cannot exist in the right half. We can discard that entire section.
3. If nums[mid] < target, all elements to the left of mid are smaller than target. The target cannot exist in the left half, and we can discard it.

This logic allows us to reduce the search space by half in every iteration.

Visual Description: Imagine the search space defined by two pointers, left and right. Initially, they encompass the entire array. We calculate the mid point. If the value at mid is not the target, one of the pointers moves past mid, effectively "closing" the window on the half of the array that cannot contain the target. This window shrinks exponentially until the target is found or the pointers cross, indicating the search space is empty.

Execution Flow

Let's trace the algorithm with nums = [-1, 0, 3, 5, 9, 12] and target = 9.

1. Start: left = 0, right = 5. Search space is indices [0, 5].
2. Iteration 1:
   • left <= right (0 <= 5) is true.
   • Calculate mid: 0 + (5 - 0) / 2 = 2.
   • nums[2] is 3.
   • Compare 3 with target (9). Since 3 < 9, target is in the right half.
   • Update left to mid + 1 = 3.
   • New search space: indices [3, 5].
3. Iteration 2:
   • left <= right (3 <= 5) is true.
   • Calculate mid: 3 + (5 - 3) / 2 = 4.
   • nums[4] is 9.
   • Compare 9 with target (9). They are equal.
   • Return: 4.

Proof of Correctness

The correctness of this algorithm relies on the invariant that if the target exists in the array, it must be located within the current interval [left, right].

1. Initialization: At the start, the interval is the entire array [0, n-1]. If the target exists, it is trivially within this range.
2. Maintenance: In each step, we compare target with nums[mid].
   • If nums[mid] < target, then for all i <= mid, nums[i] < target (due to sorting). Thus, the target cannot be in [left, mid]. By setting left = mid + 1, we preserve the invariant that the target is in the new range [mid + 1, right].
   • If nums[mid] > target, then for all i >= mid, nums[i] > target. The target cannot be in [mid, right]. By setting right = mid - 1, we preserve the invariant for the new range [left, mid - 1].
3. Termination: The loop terminates when left > right. This implies the search interval is empty. Since the invariant guarantees the target would be in the interval if it existed, an empty interval proves the target is not present in the array.

Reference Implementation

C++ Solution for LeetCode 704

cpp
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            // Prevent potential integer overflow
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                // Target is in the right half
                left = mid + 1;
            } else {
                // Target is in the left half
                right = mid - 1;
            }
        }

        return -1;
    }
};

Java Solution for LeetCode 704

java
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            // Calculate mid to avoid overflow
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                // Target is in the upper half
                left = mid + 1;
            } else {
                // Target is in the lower half
                right = mid - 1;
            }
        }

        return -1;
    }
}

Python Solution for LeetCode 704

python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        
        while left <= right:
            # Integer division in Python
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                # Target must be to the right
                left = mid + 1
            else:
                # Target must be to the left
                right = mid - 1
                
        return -1

Why does my code fail on single-element arrays?

• Mistake: Using the loop condition while (left < right) instead of while (left <= right).
• Why: When left == right, the search interval contains exactly one element. If the condition is strict inequality (<), the loop terminates before checking this final element.
• Consequence: If the target is at that specific index, the algorithm returns -1 incorrectly.

Why is (left + right) / 2 considered risky?

• Mistake: Calculating the midpoint as (left + right) / 2 in languages with fixed-size integers (like C++ or Java).
• Why: If left and right are both large positive integers (near INT_MAX), their sum can overflow into a negative number before division.
• Consequence: Accessing nums[mid] with a negative index will cause a runtime error (Index Out of Bounds) or undefined behavior. Use left + (right - left) / 2.