Binary Search

The obvious approach: check every element until you find the target. It’s correct, but it completely ignores the one piece of extra information the problem hands you for free — the array is sorted — which is exactly what the O(log n) requirement is hinting you should exploit.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i, num in enumerate(nums):
            if num == target:
                return i
        return -1

Because the array is sorted, checking the middle element tells you which half the target must be in (if it’s present at all) — so you can discard the other half entirely, every time. Repeat on the shrinking window until you find the target or the window is empty.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1

Watch each probe: it compares the middle element against the target and then prunes the entire half that cannot contain it, so the window halves on every step.

Why it’s correct: sortedness guarantees that if nums[mid] < target, every index ≤ mid is also < target and can be safely discarded (symmetric argument for >). No valid answer is ever thrown away. Complexity: the search window halves every iteration, so after k steps only n / 2^k elements remain — reaching a single element takes k = log₂ n steps → O(log n) time, O(1) space.