Почему следует рассматривать сложность времени выполнения бинарного поиска как log2N

Подумайте об этом так:

Если вы можете позволить себе сократить что-то вдвое m раз (т. е. вы можете позволить себе потратить время, пропорциональное m), то какой большой массив вы можете себе позволить для поиска?

Очевидно, массивы размером 2^m, верно?

Таким образом, если вы можете выполнить поиск в массиве размером n = 2^m, то время, которое потребуется, пропорционально m, и решение m для n выглядит так:

п = 2^м

log₂(n) = log₂(2^m)

log₂(n) = m


Другими словами: выполнение двоичного поиска в массиве размером n = 2^{m< /sup>} занимает время, пропорциональное m или, что то же самое, пропорциональное log₂(n).

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

давайте возьмем пример, чтобы решить проблему.

предположим, что у нас есть «n» яблок, и каждый день половина яблок гниет. то через сколько дней количество яблок будет «1».

первый день n яблок : a a a a .... (всего n)

второй день: a a a a..a(всего n/2)

третий день: a a a .. a (всего n/(2^2));

так далее............... предположим, что через k дней останется 1 яблок
т.е. n/(2^k) должно стать 1 в конце

п/(2^к)=1; 2^к=п; прикладывание бревна к основанию 2 с обеих сторон

k=log n;

так же и в бинарном поиске

сначала у нас осталось n элементов, затем n/2, затем n/4, затем n/8, так что, наконец, у нас остался один элемент, поэтому временная сложность равна log n