Binary Search without Sorting

Consider the following binary search code in Python :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def binary_search(L,x):
    lo = 0
    hi = len(L) - 1
    while lo <= hi:
        mid = (lo + hi) / 2

        if L[mid] == x:
            return True
        elif L[mid] > x:
            hi = mid - 1
        elif L[mid] < x:
            lo = mid + 1
    return False

It works perfectly, unless if you forgot to sort \(L\) in the first place! Given that \(L\) is a permutation of 0 to 6 and \(x\) is an integer in \(L\), how many distinct inputs \((L,x)\) are there such that the code still works?

×

Problem Loading...

Note Loading...

Set Loading...