Binary search uses ordering to locate a value without scanning every element. On a sorted list, it repeatedly narrows the candidate range by comparing against a middle element, making lookup take O(log n) comparisons. section 5.1.2
A sorted word list uses C#’s BinarySearch for membership and prefix navigation. A nonnegative result identifies an exact match; a negative result encodes the insertion position through its bitwise complement. Starting there, iteration continues until words stop matching the prefix. section 5.1.2
Binary search is useful, but its surrounding costs matter:
- String lookup costs O(m log n), because each of O(log n) comparisons may inspect strings of length m. section 5.1.2
- Prefix search adds one O(m) StartsWith check per matching word and can therefore approach O(mn) when most entries share the prefix. section 5.1.2
- Categorical sampling can binary-search cumulative ladder heights in O(log n), but repeated equal heights from zero-weight categories require careful tie handling. section 12.9
Finding a prefix range
Given a sorted list of words, search for "cat". If no exact "cat" exists, complement the negative BinarySearch result to obtain the first possible insertion position, then yield consecutive words while StartsWith("cat") remains true. section 5.1.2
Listing 5.1 A sorted word list
class SortedWordList : IWords
{
private List<string> words;
public SortedWordList(List<string> words) #1
{
this.words = words;
}
public bool Contains(string word) => words.BinarySearch(word) >= 0; #2
public IEnumerable<string> StartsWith(string prefix)
{
int i = words.BinarySearch(prefix);
if (i < 0)
i = ~i; #3
for (; i < words.Count; i += 1)
{
string w = words[i];
if (!w.StartsWith(prefix)) #4
yield break;
yield return w;
}
}
public IEnumerator<string> GetEnumerator() => words.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
Inspect the compact C# implementation of membership testing, insertion-position recovery, and lazy prefix enumeration. section 5.1.2
