Бинарный поиск

Допустим, что у нас есть отсортированный массив чисел:
1 2 6 8 56 234 745 998 1010

Как нам определить, что в этом массиве есть какое-то число?
Самый простой вариант - пройти линейно от первого элемента до последнего. Таким образом мы получаем O(n) (Если кто не видел пост https://t.me/unsafecsharp/97).

Но как это сделать быстрее?
На этом месте те, кто не знает, может остановиться и подумать

На самом деле существует небольшой лайфхак: если вы видите что-нибудь отсортированное (массив это или матрица - не важно) и задача - поиск, то сложность всегда будет log(n). В теории можно придумать алгоритм, который будет еще умнее, но сложность от этого не изменится.

Итак, для начала нам нужно взять центральный индекс, то есть length / 2. После чего у нас массив разделится на два подмассива, при этом слева элементы будут всегда меньше искомого, а справа - больше.
Т.е. если центральный элемент не тот, который мы ищем, то мы сразу отсеиваем половину элементов массива и берем индекс снова центральный от подмассива.
Ищем 2:
[1 2 6 8 56 234 745 998 1010]
[1 2 6 8 56]
[1 2 6]

Т.е. мы за 3 итерации нашли число. Вот это отбрасывание половины и есть log(n).

#search #binary #code #algorithms