[room] on binary search and merge-sort algos

[room] on binary search and merge-sort algos

[Michael Shigorin]

	Здравствуйте.
http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
"почти все бинарные поиски и сортировки слиянием сломанные"

2 Bcc: надеюсь, вы [пока] не против такого спама? :)

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/

Re: [room] on binary search and merge-sort algos

[Denis Kirienko]

Michael Shigorin пишет:
> 	Здравствуйте.
> http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
> "почти все бинарные поиски и сортировки слиянием сломанные"

А я бы у школьника на зачете такой бинарный бы поиск не принял.
Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
возможных случая.

--
Денис

Re: [room] on binary search and merge-sort algos

[Damir Shayhutdinov]

>         Здравствуйте.
> http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
> "почти все бинарные поиски и сортировки слиянием сломанные"

Ошибка тут в том, что mid объявлен как int, а не как unsigned. Так же,
как low и high.

Если индекс массива - неотрицательное число (а это как правило именно
так, кроме сложных случаев указательной арифметики), то и тип надо
ставить неотрицательный (unsigned). Тогда приведение к unsigned будет
излишним.

Re: [room] on binary search and merge-sort algos

[Damir Shayhutdinov]

> А я бы у школьника на зачете такой бинарный бы поиск не принял.
> Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
> возможных случая.
Если уж придираться - то по полной. Там на самом деле четыре возможных
случая, включая проверку в while (low <= high).

Re: [room] on binary search and merge-sort algos

[Denis Kirienko]

Damir Shayhutdinov пишет:
>> А я бы у школьника на зачете такой бинарный бы поиск не принял.
>> Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
>> возможных случая.
> Если уж придираться - то по полной. Там на самом деле четыре возможных
> случая, включая проверку в while (low <= high).

А вот этого я уже не понимаю. Условие-то в цикле должно быть по-любому,
от него никуда не денешься.

Суть бинарного поиска в том, что массив на каждом шаге делится на две
части, между которыми осуществляется выбор. В том алгоритме, который
приведён по ссылке массив делится на три части.

--
Денис

Re: [room] on binary search and merge-sort algos

[Damir Shayhutdinov]

> >> А я бы у школьника на зачете такой бинарный бы поиск не принял.
> >> Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
> >> возможных случая.
> > Если уж придираться - то по полной. Там на самом деле четыре возможных
> > случая, включая проверку в while (low <= high).
>
> А вот этого я уже не понимаю. Условие-то в цикле должно быть по-любому,
> от него никуда не денешься.
Смотря что в условие поставить.
>
> Суть бинарного поиска в том, что массив на каждом шаге делится на две
> части, между которыми осуществляется выбор. В том алгоритме, который
> приведён по ссылке массив делится на три части.

Если вы условие выхода из цикла не считаете за "деление массива",
тогда третью часть можно вынести в это условие цикла.

unsigned low = 0;
unsigned mid = 0;
unsigned high = a.length - 1;

while (low <= high && a[mid] != key)
{
   mid = (low + high)  / 2;
   if (a[mid] < key)
      low = mid + 1;
   else
      high = mid - 1;
}
if (a[mid] == key) return mid;
return -(low + 1);

Re: [room] on binary search and merge-sort algos

[Denis Kirienko]

Damir Shayhutdinov пишет:

> Если вы условие выхода из цикла не считаете за "деление массива",
> тогда третью часть можно вынести в это условие цикла.
> 
> unsigned low = 0;
> unsigned mid = 0;
> unsigned high = a.length - 1;
> 
> while (low <= high && a[mid] != key)
> {
>    mid = (low + high)  / 2;
>    if (a[mid] < key)
>       low = mid + 1;
>    else
>       high = mid - 1;
> }
> if (a[mid] == key) return mid;
> return -(low + 1);

То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
одного условия вынесена в условие цикла.

--
Денис

Re: [room] on binary search and merge-sort algos

[Damir Shayhutdinov]

> То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
> одного условия вынесена в условие цикла.

Тогда вы просто слишком формально относитесь к понятию "бинарный поиск".

Если я правильно понимаю, то, что вы назовете бинарным поиском, будет
_всегда_ выполняться за O(log n).

А этот алгоритм "тернарного" поиска будет выполняться за O(log n)
только в _худшем_ случае.

Re: [room] on binary search and merge-sort algos

[Denis Kirienko]

Damir Shayhutdinov пишет:

>> То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
>> одного условия вынесена в условие цикла.

> Тогда вы просто слишком формально относитесь к понятию "бинарный поиск".

Может быть.

> Если я правильно понимаю, то, что вы назовете бинарным поиском, будет
> _всегда_ выполняться за O(log n).

Да.

> А этот алгоритм "тернарного" поиска будет выполняться за O(log n)
> только в _худшем_ случае.

И всё равно за O(log n) в среднем...

--
Денис

Re: [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). Найдете сами или подсказать?

--
Денис

Re: [room] on binary search and merge-sort algos

[Alexey Voinov]

Michael Shigorin <mike@osdn.org.ua> writes:

> 	Здравствуйте.
> http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
> "почти все бинарные поиски и сортировки слиянием сломанные"
Хмм.. а как насчёт реализация на языках, в которых проблема
переполнения целых как бы и не очень актуальна? :)

-- 
Best Regards!
Alexey Voinov

voins@voins.program.ru
voins@altlinux.ru

Re: [room] on binary search and merge-sort algos

[Damir Shayhutdinov]

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

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

С этим можно бороться, если заменить на high = mid; быстродействие не
должно сильно пострадать.

Re: [room] on binary search and merge-sort algos

[Michael Shigorin]

On Mon, Aug 20, 2007 at 09:07:38PM +0400, Alexey Voinov wrote:
> > http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
> > "почти все бинарные поиски и сортировки слиянием сломанные"
> Хмм.. а как насчёт реализация на языках, в которых проблема
> переполнения целых как бы и не очень актуальна? :)

Вот в комментариях народ на ту же тему и прошёлся ;)

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/