First occurrence or floor index in a sorted array: Frontier Interview's solution

Question: First occurrence or floor index in a sorted array

Companies: Microsoft

Difficulty: Medium

Problem statement

You are given an array nums of integers sorted in non-decreasing order. It may contain repeated values. You are also given an integer target.

Implement search_first_or_floor(nums, target) -> int:

If target appears in nums, return the index of its first occurrence.
Otherwise, return the index of the closest element that is less than or equal to target (its floor). If that value repeats, return the copy nearest to where target would be inserted, which is its last copy.
If every element is greater than target (or nums is empty), return -1.

Your solution should run in O(log n) time.

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i], target <= 10^9
nums is sorted in non-decreasing order.

Example 1

nums = [4, 6, 6, 6, 11], target = 6
Output: 1

6 appears at indices 1, 2 and 3, so the first occurrence is index 1.

Example 2

nums = [4, 6, 6, 6, 11], target = 9
Output: 3

9 is absent. The largest value not above it is 6, and its copy nearest the insertion point is at index 3. For target = 2 the answer would be -1.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

The question asks two things at once:

If target is in the array, return the index of its first occurrence.
If it is not, return the index of the floor: the closest element that is
<= target. If every element is larger than target, there is no floor, so
return -1.

Settle two details with the interviewer before you code. First, what to return
when no floor exists (we return -1). Second, which copy of the floor value to
return when it repeats. We return the index just left of where target would
be inserted. That is the copy positionally closest to the target, and it is
the last copy of the floor value.

Brute force. Scan left to right. Return the first index whose value equals
target. Otherwise remember the last index whose value is < target. This is
O(n) and ignores that the array is sorted. Say it in one sentence and move on.

One lower-bound search answers both cases. Let lo be the first index
whose value is >= target (the insertion point, bisect_left).

If lo < n and nums[lo] == target, then lo is the first occurrence.
Every element before lo is < target, so no earlier copy exists.
Otherwise target is absent. Every element before lo is < target and
every element from lo on is > target. The largest value <= target is
therefore nums[lo - 1], and the answer is lo - 1. When lo == 0, that is
-1, which is exactly "no floor".

Invariant for the loop. Keep a half-open window [lo, hi) with:

every index < lo holds a value < target;
every index >= hi holds a value >= target.

Start with lo = 0, hi = n. Each step looks at mid = (lo + hi) // 2. If
nums[mid] < target, set lo = mid + 1, otherwise set hi = mid. The window
shrinks every step and ends with lo == hi at the insertion point. The key
point for duplicates: on equality we move hi left and do not return early,
so we land on the first copy.

The half-open form avoids the usual off-by-one bugs. mid is always a valid
index, and the loop always terminates.

Code

from typing import Sequence


def lower_bound(nums: Sequence[int], target: int) -> int:
    """First index i with nums[i] >= target (len(nums) if none)."""
    lo, hi = 0, len(nums)
    # Invariant: nums[:lo] < target, nums[hi:] >= target.
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def search_first_or_floor(nums: Sequence[int], target: int) -> int:
    """
    If target is present, return the index of its first occurrence.
    Otherwise return the index of the closest element <= target,
    or -1 if every element is greater than target.
    """
    i = lower_bound(nums, target)
    if i < len(nums) and nums[i] == target:
        return i
    return i - 1  # -1 when i == 0: no element <= target


def brute_force(nums: Sequence[int], target: int) -> int:
    floor = -1
    for i, x in enumerate(nums):
        if x == target:
            return i
        if x < target:
            floor = i
    return floor


if __name__ == "__main__":
    import random

    assert search_first_or_floor([1, 3, 3, 3, 7], 3) == 1
    assert search_first_or_floor([1, 3, 3, 3, 7], 5) == 3
    assert search_first_or_floor([1, 3, 3, 3, 7], 0) == -1
    assert search_first_or_floor([1, 3, 3, 3, 7], 9) == 4
    assert search_first_or_floor([], 4) == -1
    assert search_first_or_floor([5], 5) == 0
    assert search_first_or_floor([2, 2, 2, 2], 2) == 0
    assert search_first_or_floor([-8, -2, 0, 4], -5) == 0

    for _ in range(2000):
        arr = sorted(random.randint(-10, 10) for _ in range(random.randint(0, 12)))
        t = random.randint(-12, 12)
        assert search_first_or_floor(arr, t) == brute_force(arr, t), (arr, t)
    print("ok")

Complexity

search_first_or_floor: O(log n) time. It runs one binary search plus an
O(1) check. O(1) extra space.
brute_force: O(n) time and O(1) space. It is a reference for testing only.
Nothing is preprocessed, so a stream of q queries costs O(q log n) on a
fixed array.

Test cases

nums = [1, 3, 3, 3, 7], target = 3: returns 1 (first of three copies).
nums = [1, 3, 3, 3, 7], target = 5: returns 3 (floor is 3, last copy, just left of the insertion point).
nums = [1, 3, 3, 3, 7], target = 0: returns -1 (every element is larger).
nums = [1, 3, 3, 3, 7], target = 9: returns 4 (larger than everything, so the floor is the last element).
nums = [], target = 4: returns -1.
nums = [5], target = 5: returns 0.
nums = [2, 2, 2, 2], target = 2: returns 0 (all duplicates, so the first index wins).
nums = [-8, -2, 0, 4], target = -5: returns 0 (negative values, floor is -8).
Randomized: 2000 sorted arrays with heavy duplicates match the linear-scan reference.

Follow-ups

Return the first copy of the floor value instead of the last. Run the
same search, then run a second lower bound for nums[i - 1]. The cost is
still O(log n).
Return the last occurrence, or the count of the target. Use an upper
bound: the first index with value > target (change < to <=). Then
count = upper_bound - lower_bound.
Return the ceiling instead (the closest element >= target). That is
just lower_bound, with n (or -1) when it runs off the end. "Nearest by
absolute difference" compares nums[i - 1] and nums[i] and breaks ties
by an agreed rule.
Rotated sorted array with duplicates. First find the pivot (with
duplicates the worst case drops to O(n) when nums[lo] == nums[mid] == nums[hi]). Then run the same search on the correct half, or on a virtual
index (pivot + k) % n.
Unknown length or an infinite stream (only get(i) is available).
Double an upper index until get(hi) >= target or it goes out of range.
Then binary search inside [hi/2, hi]. The cost is still O(log p), where p
is the answer's position.

Interviewer expectations

Mid-level (L4)

Asks what to return when there is no floor and settles which duplicate to return.
Writes a correct binary search that does not return early on a match, so duplicates resolve to the first index.
Tests the empty array, a single element, all duplicates, and a target below or above every value.

Senior (L5)

Sees that one lower-bound search answers both cases, and explains why lo - 1 is the floor.
States the loop invariant and uses half-open bounds so no +1/-1 fixes are needed.
Checks the code against a brute force (as in the randomized test), and handles last-occurrence and ceiling variants quickly.

Staff (L6+)

Generalizes to "first index where a monotone predicate is true" and applies it to the rotated-array, unbounded-stream and answer-space follow-ups.
Discusses where the worst case degrades (rotated arrays with duplicates) and why.
Considers practical concerns: mid overflow in fixed-width languages, using bisect in production, and batching many queries (sort the queries plus two pointers, O(n + q log q)).