Рекуррентное отношение числа сравнений в бинарном поиске

Question

У меня есть сомнения в отношении рекуррентности числа сравнений в бинарном поиске.

Я читал, что повторение может быть записано как T(n) = T(n/2) + 1 на этом сайте http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L14-RecRel.htm

По моему мнению, это должно быть T(n) = T(n/2) + 2, так как в худшем случае элемент может отсутствовать в массиве, и мы в итоге делаем 2 сравнения за каждый проход.

Пожалуйста, скажите мне, прав я или нет.

Answer 1

Я думаю, вы правы.

ПО МОЕМУ МНЕНИЮ, compare a b значит мы знаем a=b, a>b или же a<b в то же время. То есть, 1 сравнение может иметь 3 разных результата.

Но для языков программирования. Мы должны использовать 2 сравнения.

if mid == x:      found it!          # 1st
else if mid < x:  search right       # 2nd
else:             search left

Вы имеете в виду == а также < 2 сравнения.

Это не влияет на результат, хотя. Потому что мы используем большие обозначения O для представления сложности. Это просто вопрос постоянного, но O обычно это не волнует

Согласно основной теореме. Или +1 или же +2 приведет к той же сложности O(log n),

То, что мы хотим, это обычно предел (Big-O), а не математическое уравнение точный результат.

Я думаю, что здесь важно то, что 1 а также 2 оба постоянное время. Мы также можем разделить ==, > в машинные инструкции, и это может быть больше, чем 2, Или, может быть, некоторые языки программирования или процессор используют сравнение, это только стоит 1 сравнение. Но это не имеет значения здесь при выполнении асимптотического анализа.

---

1. https://en.wikipedia.org/wiki/Master_theorem
2. https://en.wikipedia.org/wiki/Asymptotic_analysis