Здравствуйте, Stgl, Вы писали:

S>Прошу помочь разобраться с этими вопросами. Я действительно не вижу как это работает.



начнём с трисективного бин поиска.

desiredValue // искомое значение
int a[N]; // массив, где проводится поиск
int left = 0; // левая граница поиска 
int right = N; // правая граница поиска
// диапазон полуоткрытый [0,n)
int middle; // место биекции/триекции 
while (left < right){
    middle = left +  (right - left) / 2;
    if (desiredValue<a[middle])
        right = middle - 1;
    else if (desiredValue==a[middle])
        return middle;
    else //if(a[middle]<desiredValue)
        left = middle + 1;
}
return right;

смотри лекции Степанова почему нужно не -1 и прочий NULL , а обыденную позицию. в данном случае например right вполне ( например когда искомое больше наибольшего в массиве будет возвращёна позиция за последним,)(например когда искомое меньше наименьшего в массиве будет возвращена позиция пред первым(это уже не по феншую ))

из вышеприведенного кода можно с целью пипхола сделать исходный вариант с двумя только ветками — путём слияние равенства с одним из крайних случаев и соответствующей(через рассуждения) модификацией ветвей

ps для красоты:

desiredValue // искомое значение
int a[N]; // массив, где проводится поиск
int left = 0; // левая граница поиска 
int right = N; // правая граница поиска
// диапазон полуоткрытый [0,n)
int middle; // место биекции/триекции 
while(left < right){
    switch(sign(desiredValue-a[middle = left +  (right - left)/2]){
       case -1:right = middle - 1;continue;
       case  0:return middle;
       case  1:left = middle + 1;continue;
    }
}
return right;

pps. лучше писать чуть (не более чем в 2 раза) более медленный поиск в упорядоченном массиве, чем ошибочный быстрый.

ну а вообще реальным программистам бинарный поиск писать за карьеру редко кому надо