Binary Search Solution

Problem

Given a sorted array of integers and a target value, return the index of the target. If the target is not found, return -1. The catch: you must achieve O(log n) runtime, which means you can't just scan every element.

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 is at index 4 in the array.

Counter-example: target = 2 → return -1 because 2 does not appear anywhere in the array.

Intuition

Because the array is sorted, any element splits it into two halves where everything on the left is smaller and everything on the right is larger. If the middle element isn't the target, you can throw away the wrong half entirely. Each comparison cuts the search space in half, turning O(n) work into O(log n).

Approach 1 — Linear Scan

Iterate through every element until you find the target. This works but ignores the sorted order entirely — every element is visited even if the target could never appear in the remaining half.

Walk through the array from left to right.
At each position, compare the current value to the target.
Return the index on a match.
Return -1 if the loop finishes without finding the target.

1def search(nums: list[int], target: int) -> int:
2    for index, value in enumerate(nums):
3        if value == target:
4            return index
5        if value > target:  # sorted array — target can't appear further right
6            break
7    return -1

Time: O(n) — in the worst case (target not in array), every element is visited.
Space: O(1) — no extra memory beyond the loop variable.

Approach 2 — Binary Search

Maintain a search window with left and right pointers. At each step, check the middle element and shrink the window toward whichever half could contain the target.

Initialize left = 0 and right = len(nums) - 1.
While the window is non-empty (left <= right), compute mid = left + (right - left) // 2.
If nums[mid] == target, return mid.
If nums[mid] < target, the target must be in the right half — set left = mid + 1.
If nums[mid] > target, the target must be in the left half — set right = mid - 1.
If the window collapses without a match, return -1.

1def search(nums: list[int], target: int) -> int:
2    left, right = 0, len(nums) - 1
3
4    while left <= right:
5        mid = left + (right - left) // 2  # avoids overflow in languages with fixed int width
6
7        if nums[mid] == target:
8            return mid
9        elif nums[mid] < target:
10            left = mid + 1   # target is somewhere to the right
11        else:
12            right = mid - 1  # target is somewhere to the left
13
14    return -1

Time: O(log n) — the search window halves on every iteration.
Space: O(1) — only two pointers and a midpoint variable.

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(n)	O(1)	Unsorted arrays, or as a fallback when sorting is not guaranteed
Binary Search	O(log n)	O(1)	Any sorted array — the standard approach for all interview questions involving sorted data

Common Mistakes

Using left < right instead of left <= right — the < condition exits the loop when one element remains, causing that element to never be checked. The target could be that single element, so you need <=.
Writing mid = (left + right) / 2 — this overflows in Java and C++ when both pointers are near INT_MAX. The safe form is left + (right - left) / 2, which produces the same midpoint without risk of overflow.
Forgetting the + 1 or - 1 shift — writing left = mid instead of left = mid + 1 (or right = mid instead of right = mid - 1) causes an infinite loop when left == right, because mid equals left and the window never shrinks.
Moving the wrong pointer — after ruling out the middle element, the new boundary should exclude it. If nums[mid] < target, you know mid is not the answer, so set left = mid + 1, not left = mid.
Returning the wrong value when not found — some implementations return left (which would give the insertion point, useful for other problems) when the loop ends. For this problem, the contract is to return -1 on a miss.

Binary Search — Solution