Бинарный поиск производится в упорядоченном массиве.
При бинарном поиске искомый ключ сравнивается с ключом среднего элемента в массиве. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой или правой частях массива.
Алгоритм может быть определен в рекурсивной и нерекурсивной формах.
Бинарный поиск также называют поиском методом деления отрезка пополам или дихотомии.
Количество шагов поиска определится как
log2n↑,
где n-количество элементов,
↑ — округление в большую сторону до ближайшего целого числа.
На каждом шаге осуществляется поиск середины отрезка по формуле
mid = (left + right)/2
Если искомый элемент равен элементу с индексом mid, поиск завершается.
В случае если искомый элемент меньше элемента с индексом mid, на место mid перемещается правая граница рассматриваемого отрезка, в противном случае — левая граница.
- Подготовка. Перед началом поиска устанавливаем левую и правую границы массива:
left = 0, right = 19
- Шаг 1. Ищем индекс середины массива (округляем в меньшую сторону):
mid = (19+0)/2=9
Сравниваем значение по этому индексу с искомым:
69 < 82
Сдвигаем левую границу:
left = mid = 9
- Шаг 2. Ищем индекс середины массива (округляем в меньшую сторону):
mid = (9+19)/2=14
Сравниваем значение по этому индексу с искомым:
84 > 82
Сдвигаем правую границу:
right = mid = 14
- Шаг 3. Ищем индекс середины массива (округляем в меньшую сторону):
mid = (9+14)/2=11
Сравниваем значение по этому индексу с искомым:
78 < 82
Сдвигаем левую границу:
left = mid = 11
- Шаг 4. Ищем индекс середины массива (округляем в меньшую сторону):
mid = (11+14)/2=12
Сравниваем значение по этому индексу с искомым:
80 < 82
Сдвигаем левую границу:
left = mid = 12
- Шаг 5. Ищем индекс середины массива (округляем в меньшую сторону):
mid = (12+14)/2=13
Сравниваем значение по этому индексу с искомым:
82 = 82
Решение найдено!
Чтобы уменьшить количество шагов поиска можно сразу смещать границы поиска на элемент, следующий за серединой отрезка:
left = mid + 1
right = mid — 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
46
47
48
49
50
51
#include <stdio.h>
#include <stdlib.h> // для использования функций system()
int main()
{
int k[20]; // массив ключей основной таблицы
int r[20]; // массив записей основной таблицы
int key, i;
system("chcp 1251"); // перевод русского языка в консоли
system("cls"); // очистка окна консоли
// Инициализация ключевых полей упорядоченными значениями
k[0] = 8; k[1] = 14;
k[2] = 26; k[3] = 28;
k[4] = 38; k[5] = 47;
k[6] = 56; k[7] = 60;
k[8] = 64; k[9] = 69;
k[10] = 70; k[11] = 78;
k[12] = 80; k[13] = 82;
k[14] = 84; k[15] = 87;
k[16] = 90; k[17] = 92;
k[18] = 98; k[19] = 108;
// Ввод записей
for (i = 0; i < 20; i++)
{
printf("%2d. k[%2d]=%3d: r[%2d]= ", i, i, k[i], i);
scanf("%d", &r[i]);
}
printf("Введите key: "); // вводим искомое ключевое поле
scanf("%d", &key);
int left = 0; // задаем левую и правую границы поиска
int right = 19;
int search = -1; // найденный индекс элемента равен -1 (элемент не найден)
while (left <= right) // пока левая граница не "перескочит" правую
{
int mid = (left + right) / 2; // ищем середину отрезка
if (key == k[mid]) { // если ключевое поле равно искомому
search = mid; // мы нашли требуемый элемент,
break; // выходим из цикла
}
if (key < k[mid]) // если искомое ключевое поле меньше найденной середины
right = mid - 1; // смещаем правую границу, продолжим поиск в левой части
else // иначе
left = mid + 1; // смещаем левую границу, продолжим поиск в правой части
}
if (search == -1) // если индекс элемента по-прежнему -1, элемент не найден
printf("Элемент не найден!\n");
else // иначе выводим элемент, его ключ и значение
printf("%d. key= %d. r[%d]=%d", search, k[search], search, r[search]);
getchar(); getchar();
return 0;
}
Результат выполнения
Назад: Алгоритмы сортировки и поиска
2
3
4
5
6
7
8
9
10
{
int min=0, max=n-1;
while(min<=max){
int mid=(min+max)/2;
if(arg > arr[mid]) min=mid+1;
else return mid;
}
return -1;
}