Binary Search

Intuition

A sorted array lets us decide, from one comparison, which side of the midpoint the answer must lie on. If the middle value equals the target we are done; if it is smaller, everything to its left is too small, so we search the right side; otherwise we search the left side. Each recursive call shrinks the candidate window to half its size, which is why the number of steps grows only logarithmically with the length of the input.

Algorithm walkthrough

1. 1Start with the whole array by calling the helper with lo = 0 and hi = length - 1.
2. 2If lo ever exceeds hi the window is empty, meaning the target is absent, so return -1.
3. 3Compute mid as the midpoint of lo and hi and inspect arr[mid].
4. 4If arr[mid] equals the target return mid; if it is less than the target recurse on [mid + 1, hi]; otherwise recurse on [lo, mid - 1].
5. 5The recursion unwinds with either a found index or -1 bubbling back to the caller.

Implementation

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def helper(lo: int, hi: int) -> int:
            if lo > hi:
                return -1
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                return helper(mid + 1, hi)
            return helper(lo, mid - 1)

        return helper(0, len(nums) - 1)

Intuition

The recursive halving pattern can be flattened into a single loop. We keep two pointers marking the inclusive bounds of the still-unexplored region and repeatedly test the midpoint. Rewriting the recursion as iteration removes the call-stack overhead while keeping the same logarithmic step count, so it is the version usually preferred in production.

Algorithm walkthrough

1. 1Initialise lo to 0 and hi to the last index.
2. 2While lo is not greater than hi, compute the midpoint mid.
3. 3Return mid immediately when arr[mid] matches the target.
4. 4Move lo to mid + 1 when the midpoint value is too small, or hi to mid - 1 when it is too large.
5. 5If the loop finishes without a match, return -1.

Implementation

from typing import List


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
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1