Бинарный поиск производится в упорядоченном массиве.
При бинарном поиске искомый ключ сравнивается с ключом среднего элемента в массиве. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой или правой частях массива.
Алгоритм может быть определен в рекурсивной и нерекурсивной формах.
Бинарный поиск также называют поиском методом деления отрезка пополам или дихотомии.
Количество шагов поиска определится как 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;
}Результат выполнения аналогичен предыдущему примеру.
(left + right)/2 будет работать только до момента пока размеры left и right помещаются в их типы, как только произойдет переполнение типа всё сломается, правильно делать так как написал George:
left +(right-left)/2
Добрый день. Елена, мне очень интересна тема, которую затронул Евгений в плане утечки памяти. Прокомментируйте пожалуйста. Очень интересно!
Скорее всего, Евгений прав. Тесты я не проводила
А вы проводили тесты? При создании переменной в цикле, на каждой итерации цикла, выделяется память под новую переменную, которая опять была создана в начале цикла. Таким образом, вы постоянно занимаете время на выделение в памяти место под новую переменную, которая необходима на небольшом отрезке кода, а место которое было выделено под старую переменную, остаётся занятым в памяти до конца работы программы (или пока не отработает сборщик мусора). Таким образом, вы её не экономите а растрачиваете, пока ваш цикл ещё не закончился, создавая каждый раз новую переменную. Не нужно пожалуйста убеждать в такой практике остальных. Единственное что вы правильно сказали, так это то что она будет уничтожена в конце цикла. Причём именно она, а не остальные переменные которые были созданы во время выполнения цикла. Я думаю что лучше создать одну переменную, которая будет работать до конца программы, но будет работать, чем кучу ненужных, с которыми и работать нельзя так как даже неизвестно где они теперь в памяти остались. Вот и утечка памяти.
Что за бред?
1. Память в стеке не выделяется.
2. Объявление переменной лишь указывает компилятору по какому смещению обращаться за данными переменной и его смещение после объявления будет статичным.
3. Переменные объявляются во время компиляции, а не выполнения, поэтому нет разницы внутри цикла объявлена переменная или вне.
У меня вопрос, что если искомое значение меньше первого элемента массива или больше последнего элемента массива? Например в нашем случае если мы ищем в массиве -200 (минус) или +200 (плюс), тогда будет происходить mid — 1 или mid + 1 и потом выйдет за пределы массива и будет ошибка исполнения. Надо ли перед циклом while (left <= right) делать проверку находиться ли значение которое мы ищем внутри этого диапазона- от значения нулевого индекса до последнего? то есть проверку (псевдокод) array[0] < "наше значение" < array[last].
Если конструктивно, мой вопрос, то я имею ввиду, что в начале функции бинарного поиска надо сделать проверку — искомое значение меньше первого элемента сразу выход из функции, искомое значение больше последнего элемента сразу выход из функции. Надо такую проверку делать?
Цикл while не будет выполнен ни разу если его условие не выполнится
Правильно ли я понимаю что при делении переменных типа int результат автоматически округляется в меньшую сторону?
Да, правильно.
Сложновато будет обойтись без переменной search.
Дело в том, что если искомого элемента в массиве нет, то mid всё равно будет принимать значение какого-либо индекса массива. По окончании цикла (когда left станет больше right) у нас не будет информации, нашли мы искомый элемент на последнем проходе цикла или нет.
Спасибо!
Кстати, У Вас превосходный сайт! 🙂