Постановка задачи: в неубывающем массиве целых чисел найти номер данного элемента или вывести сообщение, что такого элемента в массиве нет.
Сначала приведем листинг программы. Попробуйте самостоятельно понять суть бинарного поиска.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
int bin_search(int* a, int n, int key) { int low=0, up=n-1, i; i=(low+up)/2; while (low<=up) { if (a[i]==key) break; else if (a[i]<key) low=i+1; else up=i-1; i=(low+up)/2; } if (low<=up) return i; return -1; } void www_itmathrepetitor_ru() { srand(time(NULL)); int* a; int n,key,index; n=10; a=new int [n]; a[0]=rand()%10; cout<<a[0]<<" "; for (int i=1; i<n; i++) { a[i]=a[i-1]+rand()%10; cout<<a[i]<<" "; } cout<<endl<<"input key: "; cin>>key; index=bin_search(a,n,key); if (index==-1) cout<<"not found"; else cout<<"index: "<<index; delete [] a; } |
Так как бинарный (двоичный) поиск работает только с упорядоченными данными, то сначала генерируем неубывающий массив. Далее определяем границы поиска в массиве (это переменные low и up, которые первоначально охватывают весь массив) и анализируем центральный относительно этих границ элемент с номером i=(up+low)/2. Если он равен key, то элемент найден и процесс поиска прекращается из-за break. Если он меньше, чем key, то в силу неубывания элементов поиск следует продолжать в левой относительно центрального элемента части. Поэтому сужаем область поиска командой up=i-1. И снова определяем центральный элемент i=(up+low)/2, но уже для новой области.
Когда мы ищем слово в справочнике, то сначала открываем книгу приблизительно в середине и смотрим в какой из получившихся двух частей продолжить поиск. Эта идея из жизни и реализована в данной программе (справочник упорядочен по алфавиту).
Код написан на С++. Индексы массива от 0 до n-1, если размер массива равен n. Результат функции поиска равен -1, если элемент не найден, иначе индекс элемента (счет начинается с 0).