# Binary Search without Sorting

Computer Science Level 5

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?

×