Off by one error in binary search (corner case)

Question

I'm having trouble with a corner case in my version of binary search. My version will output the bin which contains a 1 in the input list. The algorithm does this by testing groups of half the size of the input list respectively- upper and lower in the code below - and if the presence of a 1 is detected the algorithm moves the references around like a normal binary search and continues until it has found the 1. The list contains only 1s and 0s.

N.B. It has been pointed out to me that any() will scan the (sub)list with an O(n) operation, and so seemingly defeat the purpose of the algorithm below (which is to identify the position of a 1 by testing sub-lists). I am actively looking for a better test, and would be happy to hear any ideas, but I am (currently) actively interested in resolving this issue.

Below is the function:

def binary_search(inList):
    low = 0
    high = len(inList)

    while low < high:
        mid = (low + high) // 2
        upper = inList[mid:high]
        lower = inList[low:mid]
        if any(lower):
            high = mid
        elif any(upper):
            low = mid+1
       else:
            # Neither side has a 1
            return -1
    return mid

Here are the unit tests the above code passes:

# Test a basic case
inlist = [0] * 256
inlist[123] = 1
assert binary_search(inlist) == 123

# Test a case with odd len
inlist = [0] * 99
inlist[20] = 1
assert binary_search(inlist) == 20

# Test a case with odd len
inlist = [0] * 100
inlist[20] = 1
assert binary_search(inlist) == 20

inlist = [0]*4
inlist[1] = 1
assert binary_search(inlist) == 1

# Start
inlist = [0] * 256
inlist[0] = 1
assert binary_search(inlist) == 0

##middle
inlist = [0] * 256
inlist[128] = 1
assert binary_search(inlist) == 128

#end
inlist = [0] * 256
inlist[255] = 1
assert binary_search(inlist) == 255

#Test the case with no 1s
inlist = [0] * 8
assert binary_search(inlist) == -1

But it fails on this corner case

inlist = [0]*4
inlist[2] = 1
assert binary_search(inlist) == 2

What seems to be happening is that in the first stage everything goes as expected:

inList = [0,0,1,0]
upper = [1,0]
lower = [0,0]

However in the second stage mid, high and low all become 3 and

upper = [0]
lower = []

i.e. the 1 is missed.

I spent an hour in the debugger and modified the function to:

def binary_search(inList)
    low = 0
    high = len(inList) -1
    while low <= high:
        mid = low + (high - low) // 2
        if any(inList[low:mid]):    # <- this one
            high = mid - 1
        elif any(inList[mid + 1:high+1]): # <- this one
            low = mid + 1
        else:
            return mid
    return -1

This now passes all the tests above (and the weird cornner case) except for the all 0s test:

#Test the case with no 1s
inlist = [0] * 8
assert binary_search(inlist) == -1

I realise this is stupid, but I can't spot how to get the function to pass both tests.

Answer 1

Here's your problem:

while low <= high:
    mid = low + (high - low) // 2
    if any(inList[low:mid]):    # <- this one
        high = mid - 1
    elif any(inList[mid + 1:high+1]): # <- this one
        low = mid + 1
    else:
        return mid

Think about what happens when your list contains all 0s. The if fails, since there are no 1s in inList between low and mid. The elif also fails, as there are no 1s between mid and high. Then there's an else, which is exactly what is executed now. Hence you don't get a -1.

Your else block is exactly the part of your code that is executed when there are no 1 in inList. Therefore, if you really want to handle the case of all 0s, then you should make that block return -1

As a side-note though, I'm not sure why you would want to do anything resembling a binary search on an unsorted list.