Given a sorted (ascending) slice that may contain duplicates and a target, return
the index of the first (leftmost) occurrence of the target, or -1 if it isn't
present.
findLeftmost(nums, target)
Input format: nums | target.
[5, 7, 7, 8, 8, 10], target=8 // → 3
[5, 7, 7, 8, 8, 10], target=7 // → 1
[5, 7, 7, 8, 8, 10], target=6 // → -1
Ordinary binary search stops the instant it finds any match. Fine for distinct values, but here duplicates are allowed and you need the first occurrence — the middle element that happens to get checked could be any one of several duplicates.
Finding a match doesn't tell you whether an earlier occurrence sits further left. Returning immediately risks missing the leftmost one.
Treat this like a lower-bound search: find the first index where "is nums[i] >= target?" becomes true. Sortedness guarantees this transition happens exactly once. If that boundary index actually holds the target (not something larger), it's the leftmost occurrence.
Maintain [lo, hi]. At the middle: less than target, move lo past it. Greater than target, move hi before it. Equal to target — a candidate leftmost match — record it, but don't stop; keep narrowing into the left half in case an earlier occurrence exists. Since you always push left on a match, the last candidate recorded before the range empties is guaranteed the earliest.
Even with the added bookkeeping, each comparison still eliminates half the remaining range. A linear scan for the first occurrence takes time proportional to its position; this finds it in time proportional to the array's logarithm, regardless of where the target sits.
def find_leftmost(nums, target):
lo = 0
hi = len(nums) - 1
result = -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
result = mid
hi = mid - 1
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return result
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.