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


 

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

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

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

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

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

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

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


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

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

  • У меня вопрос, что если искомое значение меньше первого элемента массива или больше последнего элемента массива? Например в нашем случае если мы ищем в массиве -200 (минус) или +200 (плюс), тогда будет происходить mid - 1 или mid + 1 и потом выйдет за пределы массива и будет ошибка исполнения. Надо ли перед циклом while (left <= right) делать проверку находиться ли значение которое мы ищем внутри этого диапазона- от значения нулевого индекса до последнего? то есть проверку (псевдокод) array[0] < "наше значение" < array[last].

    • Если конструктивно, мой вопрос, то я имею ввиду, что в начале функции бинарного поиска надо сделать проверку - искомое значение меньше первого элемента сразу выход из функции, искомое значение больше последнего элемента сразу выход из функции. Надо такую проверку делать?

      • Елена Вставская
        Цикл while не будет выполнен ни разу если его условие не выполнится


    • Елена Вставская
      Не согласна с Вами. Переменная, объявленная в цикле, позволяет экономить память, поскольку видна только внутри этого цикла. После завершения цикла память, которая была выделена для этой переменной, освобождается.

      • Евгений
        А вы проводили тесты? При создании переменной в цикле, на каждой итерации цикла, выделяется память под новую переменную, которая опять была создана в начале цикла. Таким образом, вы постоянно занимаете время на выделение в памяти место под новую переменную, которая необходима на небольшом отрезке кода, а место которое было выделено под старую переменную, остаётся занятым в памяти до конца работы программы (или пока не отработает сборщик мусора). Таким образом, вы её не экономите а растрачиваете, пока ваш цикл ещё не закончился, создавая каждый раз новую переменную. Не нужно пожалуйста убеждать в такой практике остальных. Единственное что вы правильно сказали, так это то что она будет уничтожена в конце цикла. Причём именно она, а не остальные переменные которые были созданы во время выполнения цикла. Я думаю что лучше создать одну переменную, которая будет работать до конца программы, но будет работать, чем кучу ненужных, с которыми и работать нельзя так как даже неизвестно где они теперь в памяти остались. Вот и утечка памяти.

        • Человек
          Что за бред? 1. Память в стеке не выделяется. 2. Объявление переменной лишь указывает компилятору по какому смещению обращаться за данными переменной и его смещение после объявления будет статичным. 3. Переменные объявляются во время компиляции, а не выполнения, поэтому нет разницы внутри цикла объявлена переменная или вне.

      • Евгений04
        Добрый день. Елена, мне очень интересна тема, которую затронул Евгений в плане утечки памяти. Прокомментируйте пожалуйста. Очень интересно!

  • Сортировать и искать можно даже не прибегая к сортировке текстового массива

  • Хватов Максим
    Кстати говоря, если убрать прибавление или вычитание единицы при очередном смещении границы, то цикл while становиться бесконечным. Пример: size = 6; arr[o] = 1; arr[1] = 2; arr[2] = 3; arr[3] = 4; arr[4] = 5; arr[5] = 6; Элемент середины массива (mid)так и останется равен 4, что приведет к бесконечному циклу => искомое значение так и не будет найдено.

  • Дмитрий
    Есть задача: "Вывести на экран все числа упорядоченного массива А кратные 4 (4,8,...) с помощью бинарного поиска". Что-то я не понимаю, как к этой задаче применить бинарный поиск? К примеру у нас есть массив чисел [1, 13, 19, 21, 32]. Берем середину - 19: 19%4 != 0, а дальше что? числа кратные четырем могут быть как слева, так и справа от 19.

  • Вопрос, как поступать с поиском в тексте? Символы и слова не отсортируешь


    • Возможно Вы не нашли ответ на свой вопрос, но в программировании решаемы все задачи. Я думаю, у меня есть ответ на этот вопрос


    • Елена Вставская
      А Вы раскройте скобки, приведите подобные члены и увидите, что это та же самая формула, что и в примере.



          • Алексей Бахолдин
            (left + right)/2 будет работать только до момента пока размеры left и right помещаются в их типы, как только произойдет переполнение типа всё сломается, правильно делать так как написал George: left +(right-left)/2

  • На каждом шаге осуществляется поиск середины отрезка по формуле mid = (left - right)/2
    Здесь ошибка, не (left-right)/2 а правильно (left + right)/2

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


      • Спасибо! И еще вопрос, если позволите. Можно ли обойтись без переменной search, ведь если я правильно понимаю, это - magic number, который не дает циклу длиться бесконечно если элемент не найден, но разве не достаточно того, что у нас прописано условие
        1
        while (left <= right)
        ? Я начинающий, сейчас как раз изучаю эту тему...

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

          • Спасибо! Кстати, У Вас превосходный сайт! :)

          • 1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            int binary_search(int arr[], int n, int arg)
            {
              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;
            }

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

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