Как добавить проверку на существование элемента в алгоритм бинарного поиска?

Question

[pinguine]

Есть алгоритм бинарного поиска, который в зависимости от значения переменной last возвращает первое или последнее вхождение элемента в массив

def binary_search(l, key, last):
    low = 0
    high = len(l)-1
    while low <= high: 
        mid = (low + high) // 2
        midVal = l[mid];
        if (midVal < key or (last and midVal == key)): low = mid + 1
        elif (midVal > key or ((not last) and midVal == key)): high = mid - 1
    return high if last else low

Как добавить проверку на существование элемента в алгоритм бинарного поиска? Проверка типа if key in list не подходит, так как это еще один проход по массиву в цикле.

Answer 1

[apreci]

def binary_search(elem, array):
    left = 0
    right = len(array)

    while left != right:
        med = (left + right) // 2

        if array[med] < elem:
            left = med + 1
        elif array[med] > elem:
            right = med
        else:
            return med

    return -1

В случае отсутствия элемента возвращается -1.

Comments

[pinguine]

Есть алгоритм бинарного поиска, который в зависимости от значения переменной last возвращает первое или последнее вхождение элемента в массив

Этот же алгоритм возвращает первое вхождение.