Implement binary search from scratch

Question

Implement binary search on a sorted integer array without using any library helpers (no bisect, Arrays.binarySearch, etc.). Provide both iterative and recursive versions, and address each of the following:

1. Basic search. Return the index of the target if it is present, or -1 if it is absent.
2. First occurrence. When the array contains duplicates, return the index of the first occurrence of the target.
3. Last occurrence. When the array contains duplicates, also be able to return the index of the last occurrence of the target.
4. Insertion index. If the target is absent, return the index at which it could be inserted while keeping the array sorted (the classic "search insert position").
5. Integer overflow. Compute the midpoint in a way that avoids integer overflow on large indices.
6. Correctness & invariants. Clearly state your loop invariant and boundary handling (inclusive vs. exclusive bounds), and argue why the search terminates and is correct.
7. Complexity. State the time and space complexity of each variant.

Example

nums = [1, 2, 2, 2, 5, 7],  target = 2
  basic search  -> any index in {1, 2, 3}
  first occ.    -> 1
  last occ.     -> 3

nums = [1, 3, 5, 6],        target = 4
  basic search  -> -1
  insertion idx -> 2

Binary Search — Basic Search

Implement binary search on a sorted integer array WITHOUT using any library helpers (no bisect, Arrays.binarySearch, etc.). Return the index of target if it is present in nums, or -1 if it is absent. The array is sorted in non-decreasing order. If the target appears multiple times, returning any valid matching index is acceptable, but these tests use distinct-value arrays for the basic search so the answer is unique.

Use an overflow-safe midpoint computation: mid = lo + (hi - lo) / 2 rather than (lo + hi) / 2.

Example:

  nums = [1, 3, 5, 6], target = 5  ->  2
  nums = [1, 3, 5, 6], target = 2  -> -1

Constraints

• 0 <= len(nums) <= 10^5
• nums is sorted in non-decreasing order
• -10^9 <= nums[i], target <= 10^9
• Do not use any built-in search helpers (bisect, Arrays.binarySearch, etc.)

Hints

1. Maintain an inclusive search window [lo, hi]. Invariant: if target exists, its index is within [lo, hi].
2. Compute the midpoint as lo + (hi - lo) // 2 to avoid integer overflow in fixed-width languages.
3. When nums[mid] < target, the answer (if any) is strictly to the right, so set lo = mid + 1; otherwise move hi = mid - 1. The loop ends when lo > hi (empty window).

Binary Search — First Occurrence (Lower Bound)

Given a sorted integer array nums (which may contain duplicates) and a target, return the index of the FIRST (leftmost) occurrence of target, or -1 if it is absent. Do not use any library helpers.

The trick: on a match, do not return immediately — record the candidate index and keep searching the LEFT half so an earlier duplicate can override it.

Example:

  nums = [1, 2, 2, 2, 5, 7], target = 2  ->  1
  nums = [1, 2, 2, 2, 5, 7], target = 4  -> -1

Constraints

• 0 <= len(nums) <= 10^5
• nums is sorted in non-decreasing order and may contain duplicates
• -10^9 <= nums[i], target <= 10^9
• Do not use any built-in search helpers

Hints

1. A plain binary search returns the first match it lands on, which may be a middle duplicate, not the leftmost one.
2. On nums[mid] == target, store mid as the best answer so far, then move hi = mid - 1 to keep probing the left half.
3. The 'equal' and 'greater' branches both move hi left, so you can merge them: if nums[mid] >= target, go left; else go right — recording the index only on exact equality.

Binary Search — Last Occurrence (Upper Bound)

Given a sorted integer array nums (which may contain duplicates) and a target, return the index of the LAST (rightmost) occurrence of target, or -1 if it is absent. Do not use any library helpers.

Mirror image of first-occurrence: on a match, record the candidate index and keep searching the RIGHT half so a later duplicate can override it.

Example:

  nums = [1, 2, 2, 2, 5, 7], target = 2  ->  3
  nums = [5, 5, 5, 5],       target = 5  ->  3

Constraints

• 0 <= len(nums) <= 10^5
• nums is sorted in non-decreasing order and may contain duplicates
• -10^9 <= nums[i], target <= 10^9
• Do not use any built-in search helpers

Hints

1. Symmetric to first-occurrence: record the match, then continue into the right half instead of the left.
2. On nums[mid] == target, store mid and set lo = mid + 1. The 'equal' and 'less' branches both move lo right, so they can be merged.
3. Because lo only ever increases and hi only ever decreases by at least one each iteration, the window strictly shrinks and the loop terminates when lo > hi.

Binary Search — Insertion Index (Search Insert Position)

Given a sorted integer array nums (distinct or with duplicates) and a target, return the index where target is found, OR — if it is absent — the index at which it could be inserted to keep the array sorted. This is the classic lower-bound search. Do not use any library helpers.

Use a half-open interval [lo, hi). When the loop ends, lo equals the number of elements strictly less than target, which is exactly the insertion point (and, if present, the index of the first occurrence).

Example:

  nums = [1, 3, 5, 6], target = 5  ->  2  (present)
  nums = [1, 3, 5, 6], target = 2  ->  1  (insert before 3)
  nums = [1, 3, 5, 6], target = 7  ->  4  (append at end)

Constraints

• 0 <= len(nums) <= 10^5
• nums is sorted in non-decreasing order
• -10^9 <= nums[i], target <= 10^9
• Do not use any built-in search helpers

Hints

1. Use a half-open window [lo, hi) with hi initialized to len(nums), not len(nums) - 1. Invariant: every index < lo has value < target, every index >= hi has value >= target.
2. When nums[mid] < target, move lo = mid + 1; otherwise keep mid as a candidate with hi = mid (do NOT use mid - 1 here).
3. The loop ends when lo == hi; that common value is the lower bound — the first position whose value is >= target, i.e. the insertion point (and the first-occurrence index if target is present).

Solution

One skeleton powers every variant; the only differences are (a) the comparison branch and (b) what you do on a match. For plain search you return immediately; for first/last occurrence you record the match and continue toward the left/right; for the insertion index you use a half-open lower-bound search whose terminal lo is the insert position. The discriminating signals interviewers look for: an overflow-safe midpoint (lo + (hi - lo) // 2), a clearly stated loop invariant with consistent inclusive vs. half-open bounds, correct duplicate handling, and a clean O(log n) time / O(1) iterative space analysis.

Core idea

Binary search exploits the sorted order to halve the search space each step. The whole family of variants below shares one skeleton; what changes is the comparison and which side we keep when we find a match.

---

1. Basic search (iterative) with overflow-safe midpoint

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1          # inclusive bounds [lo, hi]
    while lo <= hi:
        mid = lo + (hi - lo) // 2      # overflow-safe midpoint
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Overflow note. mid = (lo + hi) // 2 can overflow in fixed-width languages (Java/C++ int) when lo + hi exceeds INT_MAX. Using mid = lo + (hi - lo) // 2 keeps the intermediate value bounded by hi. (In Python integers are arbitrary precision, so this is a portability/best-practice habit, but interviewers expect you to call it out.)

1b. Basic search (recursive)

def binary_search_rec(nums, target, lo=0, hi=None):
    if hi is None:
        hi = len(nums) - 1
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        return binary_search_rec(nums, target, mid + 1, hi)
    else:
        return binary_search_rec(nums, target, lo, mid - 1)

---

2. First occurrence (lower bound)

Do not return on the first match; instead record the candidate and keep searching the left half so an earlier duplicate can override it.

def first_occurrence(nums, target):
    lo, hi, ans = 0, len(nums) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            ans = mid
            hi = mid - 1          # look further left
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

3. Last occurrence (upper bound)

Mirror image: on a match, record it and keep searching the right half.

def last_occurrence(nums, target):
    lo, hi, ans = 0, len(nums) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            ans = mid
            lo = mid + 1          # look further right
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

---

4. Insertion index (search insert position)

This is the classic lower-bound search over a half-open interval [lo, hi). When the loop ends, lo is exactly the number of elements strictly less than target, which is the insertion point. If nums[lo] == target it is also the index of the first occurrence.

def search_insert(nums, target):
    lo, hi = 0, len(nums)          # half-open [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid             # keep mid as a candidate
    return lo                     # present -> first index; absent -> insertion point

To combine "return index if present, else insertion index" in one call:

def search_or_insert(nums, target):
    i = search_insert(nums, target)
    return i if i < len(nums) and nums[i] == target else i   # both paths return i;
    # use a sentinel/flag if you must distinguish 'found' from 'would-insert-here'

---

Loop invariant & correctness

• Inclusive form [lo, hi] (used in 1-3): the invariant is "if the target exists, its index lies within [lo, hi]." Each iteration strictly shrinks the interval (lo increases or hi decreases by at least one), so it cannot loop forever; it terminates when lo > hi, i.e. the interval is empty.
• Half-open form [lo, hi) (used in 4): the invariant is "every index < lo has value < target, and every index >= hi has value >= target." The loop ends when lo == hi, at which point lo is the first position whose value is >= target — exactly the lower bound / insertion point.
• Keep the two styles consistent within a single function; mixing inclusive hi = len - 1 with a lo < hi condition (or the reverse) is the most common source of off-by-one bugs.

Complexity

• Time: O(log n) for every variant — the candidate range halves each step.
• Space: O(1) for all iterative versions. The recursive version is O(log n) stack space; it can be made O(1) if the language performs tail-call optimization, but most (including Python and Java) do not, so iterative is preferred in production.

[1, 2, 2, 2, 5, 7], target 2 -> first_occurrence = 1, last_occurrence = 3; [1, 3, 5, 6], target 4 -> basic = -1, insertion index = 2; [1, 3, 5, 6], target 5 -> basic = 2, insertion index = 2; empty array, any target -> basic = -1, insertion index = 0. Time O(log n) per variant; space O(1) iterative, O(log n) recursive.