How do I run a binary search for words that start with a certain letter?
<p>I am asked to binary search a list of names and if these names start with a particular letter, for example A, then I am to print that name.
I can complete this task by doing much more simple code such as</p>

<pre><code>for i in list:
    if i[0] == "A":
        print(i)
</code></pre>

<p>but instead I am asked to use a binary search and I'm struggling to understand the process behind it. We are given base code which can output the position a given string. My problem is not knowing what to edit so that I can achieve the desired outcome</p>

<pre><code>name_list = ["Adolphus of Helborne", "Aldric Foxe", "Amanita Maleficant", "Aphra the Vicious", "Arachne the Gruesome", "Astarte Hellebore", "Brutus the Gruesome", "Cain of Avernus"]


def bin_search(list, item):
    low_b = 0
    up_b = len(list) - 1
    found = False

    while low_b &lt;= up_b and found ==  False:
        midPos = ((low_b + up_b) // 2)
        if list[midPos] &lt; item:
            low_b = midPos + 1
        elif list[midPos] &gt; item:
            up_b = midPos - 1
        else:
            found = True
    if found:
        print("The name is at positon " + str(midPos))
        return midPos
    else:
        print("The name was not in the list.")
</code></pre>

<p>Desired outcome</p>

<pre><code>bin_search(name_list,"A")
</code></pre>

<p>Prints all the names starting with A (Adolphus of HelBorne, Aldric Foxe .... etc)</p>

<p>EDIT:
I was just doing some guess and check and found out how to do it. This is the solution code</p>

<pre><code>def bin_search(list, item):
    low_b = 0
    up_b = len(list) - 1
    true_list = []
    count = 100
    while low_b &lt;= up_b and count &gt; 0:
        midPos = ((low_b + up_b) // 2)
        if list[midPos][0] == item:
            true_list.append(list[midPos])
            list.remove(list[midPos])
            count -= 1
        elif list[midPos] &lt; item:
            low_b = midPos + 1
            count -= 1
        else:
            up_b = midPos - 1
            count -= 1
    print(true_list)
</code></pre>

<p>Not too sure if this is what you want as it seems inefficient... as you mention it seems a lot more intuitive to just iterate over the entire list but using binary search i found <a href="http://code.activestate.com/recipes/81188-binary-search/" rel="nofollow">here</a> i have:</p>

<pre class="lang-python prettyprint-override"><code>def binary_search(seq, t):
    min = 0
    max = len(seq) - 1
    while True:
        if max &lt; min:
            return -1
        m = (min + max) // 2
        if seq[m][0] &lt; t:
            min = m + 1
        elif seq[m][0] &gt; t:
            max = m - 1
        else:
            return m

index=0
while True:
    index=binary_search(name_list,"A")
    if index!=-1:
        print(name_list[index])
    else:
        break
    del name_list[index]
</code></pre>

<p>Output i get:</p>

<pre><code>Aphra the Vicious
Arachne the Gruesome
Amanita Maleficant
Astarte Hellebore
Aldric Foxe
Adolphus of Helborne
</code></pre>

python binary-search