Бинарный поиск (также известный как двоичный поиск или метод половинного деления)

Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.

Бинарный поиск — это эффективный алгоритм поиска значения в отсортированном массиве. Он работает следующим образом:

• Отсортируйте массив.
• Выберите опорную точку (середину) массива.
• Сравните значение искомого элемента с опорной точкой. Если они равны, то поиск завершён, иначе перейдите к следующему шагу.
• Если искомый элемент меньше опорной точки, исключите правую часть массива и повторите шаг 3 для левой части массива.
• Если искомый элемент больше опорной точки, исключите левую часть массива и повторите шаг 3 для правой части массива.

Этот алгоритм имеет среднюю временную сложность O(logn), где n — количество элементов в массиве

Дополнительный материал:

• Сортировка массива методом пузырька на Python
• Сортировка массива методом выбора на Python
• Сортировка массива методом вставки на Python

Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия)

 # Бинарный поиск работает в отсортированном массиве
sortmassiv=[4,15,16,19,22,33,35,40,41,42,43,50,55,66]

# Функция бинарного поиска key в mlist
def  binary_find(mlist:list,key:int):

    # Исследуемый участок списка
    index1=0
    index2=len(mlist)-1    

    # проверим крайние элементы.
    if   mlist[index1]==key:
          return index1

    if mlist[index2]==key:
         return index2    

    # в цикле проверим остальной диапазон
    while True:

        # ищем середину интервала
        tmp_seredina=(index2-index1)//2
        index_ser=index1+tmp_seredina

        # сдвига не было. поиск неудачный
        if    (tmp_seredina==0):
              return -1

        # проверяем: вдруг нашли ключ
        if mlist[index_ser]==key:
            return index_ser

        # сравниваем ключ и конец интервала
        # сдвигаем диапазон или к концу или к началу
        if   mlist[index_ser]>key:
             index2=index_ser
        else:
            index1=index_ser 

#  Тестируем программу
def test():
    print('')
    print(sortmassiv)
    print('\nЕсли ответ -1 элемента нет в списке.')
    print('Другой ответ это индекс элемента в массиве\n')
    print('Тест1  - ищем 10 -', binary_find(sortmassiv,10))
    print('Тест2  - ищем 99 -', binary_find(sortmassiv,99))
    print('Тест3  - ищем 33 -', binary_find(sortmassiv,33))
    print('Тест4  - ищем 3  -', binary_find(sortmassiv,3))
    print('Тест5  - ищем 42 -', binary_find(sortmassiv,42))
    print('Тест6  - ищем 4  -', binary_find(sortmassiv,4))
    print('Тест7  - ищем 55 -', binary_find(sortmassiv,55))
    print('Тест8  - ищем 35 -', binary_find(sortmassiv,35))
    print('Тест9  - ищем 40 -', binary_find(sortmassiv,40))
    print('Тест10 - ищем 66 -', binary_find(sortmassiv,66))
    print('Тест11 - ищем 47 -', binary_find(sortmassiv,47))
    print('Тест12 - ищем 21 -', binary_find(sortmassiv,21))

# Запускаем программу
test()

Скрин результата работы программы:

Скачать исходник программы:
Скачать из Облака

Еще алгоритмы тут: Алгоритмы.