[room] on binary search and merge-sort algos

[Denis Kirienko]

Damir Shayhutdinov пишет:
>> То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
>> одного условия вынесена в условие цикла.
> 
> Тогда вы просто слишком формально относитесь к понятию "бинарный поиск".
> 
> Если я правильно понимаю, то, что вы назовете бинарным поиском, будет
> _всегда_ выполняться за O(log n).
> 
> А этот алгоритм "тернарного" поиска будет выполняться за O(log n)
> только в _худшем_ случае.

Решил сравнить быстродействие двух вариантов поиска. Написал свой поиск
и Ваш поиск, запускал на случайных массивах размером 10^7..10^8
элементов. Быстродействие одинаковое в пределах статистической
погрешности (1-2%).

На самом деле правильно написать бинарный поиск не так-то просто.
Присланная вами реализация содержит ошибку (программа попадает в
segfault). Найдете сами или подсказать?

--
Денис