Code Logo

Marina Beacon Frequency Search

Published at05 Jan 2026
Created by
Easy 15 views
Like3

You are given a sorted list of stored beacon frequencies and a single target frequency. Find the index of the smallest stored frequency that is greater than or equal to the target. Indices are 0-based.

This is a standard lower-bound search. If the target appears in the list, return its index. If it does not appear, return the index of the first stored frequency that is larger than the target. If every stored frequency is smaller than the target, return -1.

For example, if freqs = [10,20,35,50] and target = 30, the answer is 2, pointing to the frequency 35 (the first one at least 30). If target = 20, the answer is 1 because 20 is present at index 1. If target = 60, the answer is -1 because no stored frequency is large enough. If target = 5, the answer is 0 because even the smallest frequency qualifies.

Lower-bound search is a foundational technique for range queries over sorted data. It lets you find the first element that meets a threshold, which is used in scheduling (first available slot at or after a time), database lookups (first row with a key at least a given value), and interval problems.

Edge cases include an empty list (return -1), a target smaller than every frequency (return 0), a target larger than every frequency (return -1), and duplicate frequencies equal to the target (return the first such index).

Example Input & Output

Example 1
Input
freqs = [10, 20, 35, 50], target = 30
Output
2
Explanation

35 is the first frequency >= 30, and its index is 2.

Example 2
Input
freqs = [10, 20, 35, 50], target = 60
Output
-1
Explanation

No frequency is >= 60.

Example 3
Input
freqs = [10, 20, 35, 50], target = 5
Output
0
Explanation

5 is smaller than every frequency, so the first one (index 0) qualifies.

Algorithm Flow

Recommendation Algorithm Flow for Marina Beacon Frequency Search

Solution Approach

Use binary search to find the first index where freqs[i] >= target. Whenever the middle value meets the threshold, record it as a candidate and move left to look for an earlier one. Otherwise, move right.

function marina_beacon_frequency_search(freqs, target) {
  var left = 0, right = freqs.length - 1, ans = -1;
  while (left <= right) {
    var mid = Math.floor((left + right) / 2);
    if (freqs[mid] >= target) { ans = mid; right = mid - 1; }
    else left = mid + 1;
  }
  return ans;
}

The ans variable always holds the leftmost qualifying index found so far. Each qualifying value narrows the search to the left half, and the loop continues until the window is empty. If no frequency reaches the target, ans stays -1.

Time complexity is O(log n), space complexity is O(1).

Best Answers

java
class Solution {
    public int marina_beacon_frequency_search(int[] freqs, int target) {
        int low = 0, high = freqs.length - 1;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (freqs[mid] >= target) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }
}