Бинарный поиск


 

Бинарный поиск производится в упорядоченном массиве.

При бинарном поиске искомый ключ сравнивается с ключом среднего элемента в массиве. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой или правой частях массива.

Алгоритм может быть определен в рекурсивной и нерекурсивной формах.

Бинарный поиск также называют поиском методом деления отрезка пополам или дихотомии.

Количество шагов поиска определится как

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

Реализация бинарного поиска на Си

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
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf()
#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;
}

Результат выполнения
Результат бинарного поиска


Назад: Алгоритмы сортировки и поиска

Комментариев к записи: 5

  • Шаг 1. Ищем индекс середины массива (округляем в меньшую сторону):
    mid = (19+0)/2=9

    Правильно ли я понимаю что при делении переменных типа int результат автоматически округляется в меньшую сторону?



      • Спасибо!

        И еще вопрос, если позволите. Можно ли обойтись без переменной search, ведь если я правильно понимаю, это — magic number,

        который не дает циклу длиться бесконечно если элемент не найден, но разве не достаточно того, что у нас прописано условие

        while (left <= right)?

        Я начинающий, сейчас как раз изучаю эту тему…


        • Елена Вставская

          Сложновато будет обойтись без переменной search.
          Дело в том, что если искомого элемента в массиве нет, то mid всё равно будет принимать значение какого-либо индекса массива. По окончании цикла (когда left станет больше right) у нас не будет информации, нашли мы искомый элемент на последнем проходе цикла или нет.


          • Спасибо!

            Кстати, У Вас превосходный сайт! 🙂


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *