Given a sorted list of lowercase strings items and a lowercase query string query, return all items that start with query. The result must preserve the original sorted order. Implement the search efficiently without scanning the entire list unless necessary.
Example 1:
Input: items = ["apple", "application", "banana", "band", "bandana"], query = "app"
Output: ["apple", "application"]
Explanation: Both returned strings begin with "app".
Example 2:
Input: items = ["car", "card", "care", "dog"], query = "cat"
Output: []
Explanation: No string in the list starts with "cat".
1 <= len(items) <= 10^50 <= len(query) <= 1000 <= len(items[i]) <= 100items is sorted in non-decreasing lexicographic orderitems = ["apple", "application", "banana", "band", "bandana"], query = "app"Output["apple", "application"]WhyThe matching strings form a contiguous block starting at the first string not less than "app".items = ["car", "card", "care", "dog"], query = "cat"Output[]WhyNo string begins with the prefix "cat".items = ["a", "aa", "aaa"], query = ""Output["a", "aa", "aaa"]WhyEvery string starts with the empty prefix.1 <= len(items) <= 10^50 <= len(query) <= 1000 <= len(items[i]) <= 100items is sorted in non-decreasing lexicographic orderAll strings contain only lowercase English lettersdef search_items(items, query):
