#!/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