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>You just need to found one item starting with the letter, then you need to identify the range. This approach should be fast and memory efficient.</p>

<pre><code>def binary_search(list,item):
    low_b = 0
    up_b = len(list) - 1
    found = False
    midPos = ((low_b + up_b) // 2)
    if list[low_b][0]==item:
        midPos=low_b
        found=True
    elif list[up_b][0]==item:
        midPos = up_b
        found=True
    while True:
        if found:
            break;
        if list[low_b][0]&gt;item:
            break
        if list[up_b][0]&lt;item:
            break
        if up_b&lt;low_b:
            break;
        midPos = ((low_b + up_b) // 2)
        if list[midPos][0] &lt; item:
            low_b = midPos + 1
        elif list[midPos] &gt; item:
            up_b = midPos - 1
        else:
            found = True
            break
    if found:
        while True:
            if midPos&gt;0:
                if list[midPos][0]==item:
                    midPos=midPos-1
                    continue
            break;
        while True:
            if midPos&lt;len(list):
                if list[midPos][0]==item:
                    print list[midPos]
                    midPos=midPos+1
                    continue
            break
    else:
        print("The name was not in the list.")
</code></pre>

<p>the output is</p>

<pre><code>&gt;&gt;&gt; binary_search(name_list,"A")
Adolphus of Helborne
Aldric Foxe
Amanita Maleficant
Aphra the Vicious
Arachne the Gruesome
Astarte Hellebore
</code></pre>

python binary-search