Embedding Shard Router
A vector store partitions its 384-dim embeddings into k contiguous shards, each indexed by a sorted starting boundary (the lowest-id vector each shard owns). When a query arrives with a vector id, the router has to pick the shard that owns it. The shards array is sorted by start id.
Problem
You are given an integer array shard_starts of length k that is strictly sorted ascending. shard_starts[i] is the lowest vector id owned by shard i. Given a vector id query, return the index of the shard that owns the id — that is, the largest i such that shard_starts[i] ≤ query. If query is below shard_starts[0], return −1 (no shard owns it).
Input
An integer k (1 ≤ k ≤ 10^5), the strictly ascending array shard_starts (each in [0, 10^9]), and a query (0 ≤ query ≤ 10^9). Multiple queries may be invoked.
Output
A single integer — the shard index, or −1 if the query is below all shard starts.
Constraints
- 1 ≤ k ≤ 100,000
- shard_starts is strictly increasing
- Answer must be O(log k) per query — linear scan won't pass
Examples
Example 1
Input
shard_starts = [0, 1024, 2048, 4096], query = 1500
Output
1
1500 ≥ 1024 (shard 1's start) but < 2048. So shard 1 owns it.
Example 2
Input
shard_starts = [100, 200, 300], query = 50
Output
-1
50 is below 100 — no shard owns it.
Example 3
Input
shard_starts = [10], query = 100
Output
0
Only one shard, query is at or above its start.