Some cases cause my binary search to enter into an Infinite loop
<p>I'm stuck in an infinite loop when searching for anything that is not in the list (but within the range of the list) and anything that is greater than the highest number. For example, when searching for 2 in the list <code>[1,2,5,6]</code>, my function returns index 1, which is correct. If I search for -1, it returns <code>False</code> which is correct. However, if I search for 100 or 4, it gets stuck in an infinite loop.     </p>

<pre><code>def binary_search(a_list, item):

    if not a_list:
        return False

    mid = len(a_list)//2

    print "Middle is: {}".format(a_list[mid])
    print a_list


    while len(a_list) &gt; 0:
        if a_list[mid] == item:
            return mid
        elif a_list[mid] &gt; item:
            return binary_search(a_list[:mid], item)
        elif a_list[mid] &lt; item:
            return binary_search(a_list[mid:], item) + mid
        else:
            return False

a = binary_search([1, 2, 3, 4, 6, 7, 8], 5) # infinite loop
b = binary_search([1, 2, 3, 4, 6, 7, 8], 100) # infinite loop
c = binary_search([1, 2, 3, 4, 6, 7, 8], 8) # works correctly
d = binary_search([1, 2, 3, 4, 6, 7, 8], -2) # works correctly
</code></pre>

<p>Try this.</p>

<pre><code>def binary_search(a_list, item):

    if not a_list:
        return False

    mid = len(a_list)//2

    print "Middle is: {}".format(a_list[mid])
    print a_list


    while len(a_list) &gt; 0:
        if len(a_list) == 1 and a_list[mid] != item:
            return False
        elif a_list[mid] == item:
            return mid
        elif a_list[mid] &gt; item:
            return binary_search(a_list[:mid], item)
        ##############################
        ### isssue place ###
        ####################
        elif a_list[mid] &lt; item:
            index = binary_search(a_list[mid:], item)
            if not index:
                return False
            else:
                return index + mid
        else:
            return False
        ################################
</code></pre>

<p>Hpoe this helps.</p>

python binary-search