Prefix Search I
You are given words, sorted ascending (duplicates allowed), and a prefix. Return the index of the first word that starts with prefix, or -1. Aim for O(log n) string comparisons.
words = ["a", "apple", "appz", "b"] prefix "ap" => 1 prefix "b" => 3 prefix "c" => -1 prefix "" => 0 (every word starts with "")
Up to 10^5 words of lowercase a-z, lengths up to 100.
Hints
Hint 1
Every word starting with prefix is >= prefix, and every word < prefix can't start with it — so lower_bound(prefix) is either the answer or proof there is none.
Hint 2
Check startswith once after the search; the binary search alone can't confirm the match.