ML Prep

Find the first matching index by binary search

Problem

Implement first_index(nums, target) for a list sorted in nondecreasing order. Return the first index containing target, including among duplicates, or -1 when absent. Use O(log⁡n)O(\log n) comparisons.

Reveal answer or reference solution

Search the half-open interval [lo, hi) for the first position whose value is not less than the target. Move lo past values below the target; otherwise move hi to mid. Validate the final candidate before returning it.

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

Public tests

  • first_index([], 3) → -1
  • first_index([1, 2, 2, 2, 5], 2) → 1
  • first_index([1, 2, 2, 2, 5], 4) → -1
  • first_index([1], 1) → 0
  • first_index([1, 3, 5], 1) → 0
Outcome

Previous attempts

Loading attempts saved in this browser…

    Review Screening Results