Бинарный поиск на языке Си

Бинарный (двоичный) поиск – простой алгоритм, который поможет найти нужное значение в заранее отсортированном массиве.

Классический пример алгоритма – поиск номера в телефонной книге. В ней данные отсортированы по алфавиту, а номеров может быть больше тысячи. Кто застал начало нулевых, помнит, какая это была морока… но только в том случае, если искать номер последовательно (линейный поиск).

Применяем линейный поиск

Особенности такого поиска:

1. Наличие ключа, индекс которого надо найти;
2. Перебор элементов массива по порядку;
3. Когда ключ ячейки найден, программа выводит его индекс в массиве.

Пример с массивом на 10 элементов:

#include<iostream>
using namespace std;
int main()
{
int arr[10], i, num, index;
cout<<«Введите 10 чисел: «;
for(i=0; i<10; i++)
cin>>arr[i];
cout<<«\nВведите нужное вам число: «;
cin>>num;
for(i=0; i<10; i++)
{
if(arr[i]==num)
{
index = i;
break;
}
}
cout<<«\nНомер индекса:»<<index;
cout<<endl;
return 0;
}

Вывод:

Введите нужное вам число: 5
Номер индекса: 4

Применяем бинарный поиск

Вернёмся к телефонной книге. Допустим, надо позвонить человеку с фамилией Афанасьев. Если перебирать номера по порядку, поиск займёт минуты три. Немало… А если нужно набрать Шепилова? Мы будем изучать книгу минимум час! Таков недостаток линейного поиска.

Используем двоичный поиск. Книга отсортирована по алфавиту, ergo Шепилов ближе к концу книги. Отметаем часть списка до буквы О. Книгу разделили пополам! Делим ещё надвое, отметаем до буквы Ц. Шепилов уже близко. Продолжаем делить на 2, пока не находим нужную букву и номер. Сколько времени мы сэкономили!

Итеративная реализация на C++:

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r — l) / 2;

if (arr[m] == x)
return m;

if (arr[m] < x)
l = m + 1;

else
r = m — 1;
}

return -1;
}

int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n — 1, x);
(result == -1) ? cout << «Такого элемента нет в массиве»
: cout << «Индекс искомого элемента равен » << result;
return 0;
}

Вывод:

Индекс искомого элемента равен 3.

Рекурсивная реализация проще:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 +4;

int a[N];
int n;

int k;

bool check(int dig)
{
int ele=a[dig];

if(k<=ele)
{
return 1;
}
else
{
return 0;
}
}
void binsrch(int lo,int hi)
{
while(lo<hi)
{
int mid=(lo+hi)/2;
if(check(mid))
{
hi=mid;
}
else
{
lo=mid+1;
}
}
//if a[lo] is k
if(a[lo]==k)
cout<<«Искомый элемент найден по индексу «<<lo;
else
cout<<«Такого элемента нет в массиве»;

}

int main()
{
cin>>n;
for(int i=0; i<n; i++)
{
cin>>a[i];
}
cin>>k;

binsrch(0,n);

return 0;
}

Таким образом, эффективность ЛП: O(n). Эффективность работы БП: O(log2(n))

По этой формуле (О-большое), линейный поиск обработает 1024 элемента, когда двоичный – только 10.

Задачи

1. Сколько нужно вопросов, чтобы наверняка отгадать (целое) число от 1 до 10100 , используя двоичный поиск? Ответ. 333
2. Сколько вопросов понадобится для отгадывания числа от 1 до 1000, если в качестве первого вопроса обязательно надо спросить «делится ли число на 3»? Ответ. 11
3. Сколько потребуется шагов алгоритма бинарного поиска, чтобы начиная с отрезка длины r – l = 2 дойти до отрезка длины меньше 10−10? Ответ. 34

Достоинства и недостатки БП

Достоинства:

• Простая реализация;
• Быстрота.

Недостатки:

• Работает только в массиве с упорядоченными элементами;
• Должна быть возможность обратится к любому элементу по индексу. Следовательно, структуры данных, построенные на связных списках не будут работать.