Code Logo

Marina Beacon Frequency Search

Published at05 Jan 2026
Created by
Easy 3 views
Like3

You are given a sorted list of stored beacon frequencies and a list of requested frequencies. For each request, return the smallest stored frequency that is still greater than or equal to that request.

This means you are looking for the first usable beacon, not just any bigger one. If the request is already in the list, you return that exact value. If every stored frequency is smaller than the request, the answer for that request is -1.

For example, if freqs = [10,20,35,50] and requests = [5,20,36], the answers are [10,20,50]. The request 5 uses 10, the request 20 matches exactly, and the request 36 needs the next larger choice, which is 50. If freqs = [15,30,45] and requests = [50,14], the answers are [-1,15].

So for each request, return the first stored frequency that reaches it, or -1 when no stored value is high enough.

Example Input & Output

Example 1
Input
freqs = [15,30,45], requests = [50,14]
Output
[-1,15]
Explanation

No beacon reaches 50, but 15 covers the 14 request.

Example 2
Input
freqs = [], requests = [10]
Output
[-1]
Explanation

With no stored beacons, every request is unanswered.

Example 3
Input
freqs = [10,20,35,50], requests = [5,20,36]
Output
[10,20,50]
Explanation

The closest frequencies meeting each request are 10, 20, and 50.

Algorithm Flow

Recommendation Algorithm Flow for Marina Beacon Frequency Search
Recommendation Algorithm Flow for Marina Beacon Frequency Search

Solution Approach

This is another lower bound search. Because freqs is sorted, we can binary search for the first position where freqs[mid] >= request.

For one request, the logic looks like this:

let left = 0;
let right = freqs.length;

while (left < right) {
  const mid = Math.floor((left + right) / 2);
  if (freqs[mid] >= request) {
    right = mid;
  } else {
    left = mid + 1;
  }
}

After the loop, left is the first possible answer position. If left is still inside the array, return freqs[left]. Otherwise, return -1 because every stored frequency is too small.

Do that for each request and build the result list in the same order. If there are n stored frequencies and m requests, the total running time is O(m log n).

Best Answers

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