Answer Repeated Lookup Queries Efficiently

Problem: Batched Sorted Lookups

You are given a sorted array arr of integers and a list of queries. Your task is to return the first index of each queried value in arr. If a value is not found, return -1. Since the query list may contain duplicate values, your implementation should optimize redundant searches.

Function Signature

def get_first_indices(arr: List[int], queries: List[int]) -> List[int]:

Constraints

• 1 <= len(arr) <= 10^6
• 1 <= len(queries) <= 10^5
• Values in arr and queries are within the range [-10^9, 10^9]

Examples

Example 1: Input: arr = [1, 2, 2, 2, 3, 4], queries = [2, 5, 2] Output: [1, -1, 1] Explanation: The first occurrence of 2 is at index 1. 5 is not in the array. The second query for 2 retrieves the cached result from the first query.

Edge Cases

• arr is empty or queries is empty.
• All values in arr are identical.
• All queried values are absent from arr.
• Large number of duplicate queries (e.g., millions of identical queries).

Requirements

• You must implement a binary search algorithm to find the first index.
• Use a cache to store the result of values previously searched to avoid re-calculating the same search.