title: Binary String Search - minimum bin width?
body: <p>I happen to be building the binary search in Python, but the question has more to do with binary search structure in general.</p>
  
  <p>Let's assume I have about one thousand eligible candidates I am searching through using binary search, doing the classic approach of bisecting the sorted dataset and repeating this process in order to narrow down the eligible set to iterate over.  The candidates are just strings of names,(first-last format, eg "Peter Jackson")  I initially sort the set alphabetically and then proceed with bisection using something like this:</p>
  
  <pre><code>hi = len(names)
  lo = 0
  while lo &lt; hi:
    mid = (lo+hi)//2
    midval = names[mid].lower()
    if midval &lt; query.lower():
      lo = mid+1
    elif midval &gt; query.lower():
      hi=mid
    else:
      return midval
  return None
  </code></pre>
  
  <p>This code adapted from here: <a href="https://stackoverflow.com/a/212413/215608">https://stackoverflow.com/a/212413/215608</a></p>
  
  <p>Here's the thing, the above procedure assumes a single exact match or no result at all.  What if the query was merely for a "Peter", but there are several peters with differing last names?  In order to return all the Peters, one would have to ensure that the bisected "bins" never got so small as to except eligible results.  The bisection process would have to cease and cede to something like a regex/regular old string match in order to return all the Peters.</p>
  
  <p>I'm not so much asking how to accomplish this as <em>what this type of search is called</em>...  what is a binary search with a delimited criteria for "bin size" called?  Something that conditionally bisects the dataset, and once the criteria is fulfilled, falls back to some other form of string matching in order to ensure that there can effectively be a ending wildcard on the query (so a search for a "Peter" will get "Peter Jacksons" and "Peter Edwards")</p>
  
  <p>Hopefully I've been clear what I mean.  I realize in the typical DB scenario the names might be separated, this is just intended as a proof of concept.</p>