#!/usr/bin/python3
# Binary search (no sanity checks!)
def binary_search(L, x):
left, right = 0, len(L) # L[left:right] contains x
while right - left > 1: # more than one element remaining?
mid = (right + left) // 2 # index of the middle of L[left:right]
if L[mid] > x: # is x in the left half?
right = mid # then continue with L[left:mid]
else: # or is x in the right half?
left = mid # then continue with L[mid:right]
return left