binsearch

#include <cstdlib>
#include <iostream>
using namespace std;

int binary_search(int array[],int first,int last, int value);

int main() {
 int list[10];
 for (int k=0; k<11; k++)
   list[k]=2*k+1;
 cout<< "binary search results: "<< binary_search(list,1,21,11)<<endl;
 return 0;
}

int binary_search(int array[],int first,int last, int search_key){
  int index;
  if (first > last) index = -1;
  else {
   int mid = (first + last)/2;
   if (search_key == array[mid]) index = mid;
   else if (search_key < array[mid]) index = binary_search(array,first, mid-1, search_key);
   else index = binary_search(array, mid+1, last, search_key);
  }
 return index;
}

/*
Распространенный алгоритм поиска в упорядоченных множествах. Наглядно представим, что мы ищем точку Y на графике F(x), который всегда неубывает (при всегда невозрастании смысл не изменится), пример такого графика моей кривой рукой снизу. Мы знаем, что эта точка расположена в отрезке [L; R]. Давайте возьмем среднюю точку
M=(R+L) /2 и тогда возможно три случая :
1) F(M)=Y; Да это же прелестно, мы нашли Y прямо в серединке!
2) F(M)<Y; Что-то мы мало взяли, наверное Y правее
3) F(M)>Y; Слишком далеко, Y где-то левее
Такие умозаключения мы можем делать по причине постоянного неубывания. А давайте тогда повторим все те же самые действия в той половине, где мы предполагаем найти Y.
• если Y слева, то в [L, M];
• если Y справа, то в [M, R];
• если мы вдруг оказались в ситуации, когда левая граница отрезка совпала с правой, или заехала за нее, то алгоритм надо останавливать, Y мы не нашли.
Наиболее удачный пример объяснения алгоритма бинарного поиска это игра в "Угадай число". Вы высказываете версию, а загадавший говорит больше загаданное число или меньше. Используя алгоритм бинарного поиска вы сможете отгадать загаданное число максимум за Log (R-L), где L,R - диапазон возможных значений. То есть для чисел от 1 до 1000 вам понадобится не больше 10 вопросов.
В программировании удачно применяется для поиска элементов в отсортированном массиве или для нахождения решения в какой-нибудь постоянно себя ведущей функции.
Самое частое употребление - поиск элемента в отсортированном массиве. Заострю внимание на обязательной отсортированности массива, только в этом случае он ведет себя как монотонная функция, а аргументов является индекс в массиве.
*/