LeetCode 704 Binary Search - Example and Complexity Analysis

Trace nums = [1, 3, 5, 7, 9, 11] with target = 7.

left = 0, right = 5. mid = 2. nums[2] = 5 < 7. Search right: left = 3.

left = 3, right = 5. mid = 4. nums[4] = 9 > 7. Search left: right = 3.

left = 3, right = 3. mid = 3. nums[3] = 7 == 7. Found! Return 3.

For target = 6 (not in array):

left = 0, right = 5. mid = 2. 5 < 6. left = 3.

left = 3, right = 5. mid = 4. 9 > 6. right = 3.

left = 3, right = 3. mid = 3. 7 > 6. right = 2.

left = 3 > right = 2. Exit loop. Return -1.

Each iteration halves the search space. After $k$ iterations, the space is $n / 2^k$. When this reaches $1$, $k = \log_2 n$. That's $O(\log n)$ time.

Only a few variables needed. $O(1)$ space.