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