Binary Search for Prefix

Based on my comprehensive research across multiple interview platforms and coding sites, I was unable to locate a problem with the exact title "Binary Search for Prefix" from Apple interviews. However, given the problem specification (Binary Search + Prefix + Medium difficulty + Apple), the most likely candidate is a variant of finding words in a sorted array that match a given prefix. Here is my professional reconstruction:

---

Binary Search for Prefix

Problem Description

Given a sorted array of strings and a prefix string, find all strings in the array that start with the given prefix. The key constraint is that you must use binary search to efficiently locate the range of words matching the prefix, rather than performing a linear scan through the entire array.

This problem tests your ability to adapt binary search beyond simple numeric comparisons to handle string prefix matching, which is a common real-world scenario in search engines, autocomplete systems, and dictionary lookups.

Input/Output Format

Input:

• words: A list of strings sorted in lexicographical order (lowercase English letters only)
• prefix: A string representing the prefix to search for (lowercase English letters only)

Output:

• Return a list of all strings in words that start with the given prefix, in the order they appear in the original array
• If no strings match the prefix, return an empty list

Data Types:

• Input: List[str], str
• Output: List[str]

Examples

Example 1

Input: words = ["apple", "application", "apply", "appreciate", "banana", "band", "bat"] prefix = "app"

Output: ["apple", "application", "apply", "appreciate"]

Explanation: Using binary search, we find the leftmost position where a word starts with "app" (index 0, "apple") and the rightmost position (index 3, "appreciate"). All words between these boundaries start with the prefix "app". The words "banana", "band", and "bat" do not match because they start with "b", which is lexicographically after "app".

Example 2

Input: words = ["algorithm", "apple", "apply", "approve"] prefix = "ap"

Output: ["apple", "apply", "approve"]

Explanation: Binary search identifies that words starting with "ap" begin at index 1. The prefix "ap" matches "apple", "apply", and "approve". The word "algorithm" starts with "al", which does not match the prefix "ap".

Constraints

• 1 <= words.length <= 10^5
• 1 <= words[i].length <= 50
• 1 <= prefix.length <= 50
• All strings in words are in lexicographical order
• words[i] and prefix consist of lowercase English letters only
• Time Complexity: O(log n × m) where n is the length of words array and m is the length of the prefix
• Space Complexity: O(k) where k is the number of matching words (excluding output storage)

Solution Hint

Use binary search twice: first to find the leftmost index of a word that could match the prefix (using the prefix as a comparison key), and second to find the rightmost matching index. The key is implementing a custom comparator that compares the prefix against only the first characters of each word in the array, allowing you to determine if a word "contains" the prefix or falls before/after it lexicographically. Once you have the range boundaries, extract all words within that range.