# Szukanie polowkowe
# binary_search
#
# www.algorytm.org

def binary_search(value, data):
    #poczatkowe zainicjowanie granic szukania
    left = 0
    right = len(data)-1
    #szukaj dopoki granica lewa jest mniejsza od prawej
    while left < right:
        middle = (left+right)//2  #wybor elementu srodkowego
        if data[middle] < value:  #jezeli element srodkowy jest mniejszy od szukanego
            left = middle + 1     #to odrzuc lewa polowke (przesun lewa granice)
        else:                     #w przeciwnym razie
            right = middle        #odrzuc prawa polowke (przesun prawa granice)
    #sprawdz czy znaleziono szukany element
    if data[right] == value:
        return right
    else:
        return None

if __name__ == '__main__':
    x = [0, 2, 3, 8, 9]
    x.sort()
    print binary_search(8,x)