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

["Damir Shayhutdinov" <lost404@gmail.com>]

> >> А я бы у школьника на зачете такой бинарный бы поиск не принял.
> >> Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
> >> возможных случая.
> > Если уж придираться - то по полной. Там на самом деле четыре возможных
> > случая, включая проверку в 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);