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/
> > "почти все бинарные поиски и сортировки слиянием сломанные"
> Хмм.. а как насчёт реализация на языках, в которых проблема
> переполнения целых к
> Решил сравнить быстродействие двух вариантов поиска. Написал свой поиск
> и Ваш поиск, запускал на случайных массивах размером 10^7..10^8
> элементов. Быстродействие одинаковое в пределах статистической
> погрешности (1-2%).
Вообще странно, должна быть разница где-то в 2 раза.
> На самом деле пр
Michael Shigorin <[EMAIL PROTECTED]> writes:
> Здравствуйте.
> http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
> "почти все бинарные поиски и сортировки слиянием сломанные"
Хмм.. а как насчёт реализация на языках, в которых проблема
переполнения целых как
Damir Shayhutdinov пишет:
>> То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
>> одного условия вынесена в условие цикла.
>
> Тогда вы просто слишком формально относитесь к понятию "бинарный поиск".
>
> Если я правильно понимаю, то, что вы назовете бинарным поиском, будет
Damir Shayhutdinov пишет:
>> То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
>> одного условия вынесена в условие цикла.
> Тогда вы просто слишком формально относитесь к понятию "бинарный поиск".
Может быть.
> Если я правильно понимаю, то, что вы назовете бинарным поиск
> То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
> одного условия вынесена в условие цикла.
Тогда вы просто слишком формально относитесь к понятию "бинарный поиск".
Если я правильно понимаю, то, что вы назовете бинарным поиском, будет
_всегда_ выполняться за O(log n).
А
Damir Shayhutdinov пишет:
> Если вы условие выхода из цикла не считаете за "деление массива",
> тогда третью часть можно вынести в это условие цикла.
>
> unsigned low = 0;
> unsigned mid = 0;
> unsigned high = a.length - 1;
>
> while (low <= high && a[mid] != key)
> {
>mid = (low + high) /
> >> А я бы у школьника на зачете такой бинарный бы поиск не принял.
> >> Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
> >> возможных случая.
> > Если уж придираться - то по полной. Там на самом деле четыре возможных
> > случая, включая проверку в while (low <= high).
>
> А
Damir Shayhutdinov пишет:
>> А я бы у школьника на зачете такой бинарный бы поиск не принял.
>> Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
>> возможных случая.
> Если уж придираться - то по полной. Там на самом деле четыре возможных
> случая, включая проверку в while (low
> А я бы у школьника на зачете такой бинарный бы поиск не принял.
> Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
> возможных случая.
Если уж придираться - то по полной. Там на самом деле четыре возможных
случая, включая проверку в while (low <= high).
___
> Здравствуйте.
> http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
> "почти все бинарные поиски и сортировки слиянием сломанные"
Ошибка тут в том, что mid объявлен как int, а не как unsigned. Так же,
как low и high.
Если индекс массива - неотрицательное
Michael Shigorin пишет:
> Здравствуйте.
> http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
> "почти все бинарные поиски и сортировки слиянием сломанные"
А я бы у школьника на зачете такой бинарный бы поиск не принял.
Поскольку он не бинарный, а тернарный -
Здравствуйте.
http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
"почти все бинарные поиски и сортировки слиянием сломанные"
2 Bcc: надеюсь, вы [пока] не против такого спама? :)
--
WBR, Michael Shigorin <[EMAIL PROTECTED]>
-- Linux.Kiev http:/
13 matches
Mail list logo
