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

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

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

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

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

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

Количество шагов поиска определится как 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.

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
#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;
}

Результат выполнения

Реализация бинарного поиска на Си: рекурсивный способ.

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
#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;
}

Результат выполнения аналогичен предыдущему примеру.

Прокрутить вверх