Бинарный (двоичный) поиск в массиве

Всем привет! Настало время позаниматься Информатикой.

Сегодня мы разберём, что такое бинарный поиск.

Задача: Написать программу, которая ищет индекс элемента в отсортированном по возрастанию массиве целых чисел. На вход подаётся значение элемента, программа выводит индекс этого элемента, если такой элемент имеется в массиве. Если такого элемента нет в массиве, программа должна вывести сообщение. Если таких элементов несколько, вывести индекс любого найденного элемента.

Данная задача отлично подходит для изучения и закрепления темы "Массивы" на уроках Информатики в 10 классе.

Решение:
Задачу мы будем решать с помощью бинарного поиска (или метода деления пополам, или дихотомии). Данный метод работает только в отсортированном массиве. Этот метод заключается в том, что мы отсекаем по половине нашего диапазона поиска, пока не найдем нужный элемент. Поэтому и метод называется бинарный поиск, из-за того ,что диапазон поиска с каждым проходом уменьшается в два раза.

Пусть у нас есть отсортированный массив:

 myArr[0] = 3;
 myArr[1] = 23;
 myArr[2] = 24;
 myArr[3] = 35;
 myArr[4] = 36;
 myArr[5] = 44;
 myArr[6] = 47;
 myArr[7] = 49;
 myArr[8] = 51;
 myArr[9] = 53;
 myArr[10] = 54;
 myArr[11] = 55;
 myArr[12] = 55;
 myArr[13] = 59;
 myArr[14] = 63;
 myArr[15] = 63;
 myArr[16] = 64;
 myArr[17] = 67;
 myArr[18] = 78;
 myArr[19] = 90;

Нам, к примеру, надо найти индекс элемента, значение которого равно 59.

Для начала найдём середину массива:
index = (19+0)/2 = 9 (округляем в меньшую сторону)

Если бы мы попали в наш элемент, то сразу бы вывели ответ. Но у 9-ого индекса значение 53. У нас 53 < 59. Т.к. массив отсортирован по возрастанию, то значит наш элемент находится в той половине, где числа >=53, т.е. в правой половине массива. И теперь все действия необходимо повторить для правой половинки.

Опять ищем середину, но теперь для правой половинки. Проверяем средний элемент. Если попали, то печатаем ответ. Если нет, то сравниваем наш средний элемент правой половинки с искомым элементом, и опять сокращаем диапазон поиска в 2 раза. И т.д.

Сдвигаем левую границу поиска. Теперь наш диапазон [9:19].Ищем середину диапазона: index = (9+19)/2 = 14
14-ый элемент это 63. Не равно нашему искомому 59.

Т.к. 59<63, то сдвигаем правую границу поиска. Теперь наш диапазон [9:14]. Ищем середину диапазона. Берём index = (9+14)/2 = 11
11-ый элемент не равен 59, значит ищем дальше!

55>59 => Сдвигаем левую границу поиска. Теперь наш диапазон [11:14]. Ищем середину диапазона: index = (11+14)/2 = 12

12-ый элемент опять не равен нашему элементу
55 > 59 => Сдвигаем левую границу. Теперь наш диапазон [12:14]. Ищем середину диапазона: index = (12+14)/2 = 13.

Тринадцатый элемент нам подходит! 59 = 59.
Ответ: 13.

Бинарный поиск - поиск элемента в массиве

Бинарный поиск - поиск элемента в массиве

Бинарный поиск намного эффективней, чем сравнивать перебором. Время работы бинарного поиска примерно: log2n

Код реализуем на языке C#. Данный язык отлично подходит для изучения информатики в школе.

Чтобы наш алгоритм был немного эффективней, при сдвиге левой границы будем добавлять единицу, при сдвиге правой отнимать единицу. Также это позволить более удобно задать условие для основного цикла.

 
 static void Main(string[] args)
 {
     // Объявляем массив
     int[] myArr = new int[20];

      // Инициализируем каждый элемент массива
      myArr[0] = 3;
      myArr[1] = 23;
      myArr[2] = 24;
      myArr[3] = 35;
      myArr[4] = 36;
      myArr[5] = 44;
      myArr[6] = 47;
      myArr[7] = 49;
      myArr[8] = 51;
      myArr[9] = 53;
      myArr[10] = 54;
      myArr[11] = 55;
      myArr[12] = 55;
      myArr[13] = 59;
      myArr[14] = 63;
      myArr[15] = 63;
      myArr[16] = 64;
      myArr[17] = 67;
      myArr[18] = 78;
      myArr[19] = 90;
            
      int left = 0; // Левая граница поиска
      int right = myArr.Length - 1; // Правая граница поиска
      int index = 0; // индекс, указывающий середину отрезка

      int q = Convert.ToInt32(Console.ReadLine()); // Запрашиваем искомое число.
      int res = -1; // Конечный результат.

      while(left <= right)
      {
           index = (right + left) / 2; ///Узнаем середину отрезка, округляем в меньшую сторону.

           // Если мы нашли искомый элемент, записываем результат и выходим из цикла.
           if (myArr[index] == q)
           {
                 res = index;
                 break;
           }
           // Меняем границы.
           if(myArr[index] < q)
           {
                 left = index+1;
           }
           else
           {
                 right = index-1;
           }
       }

       if( res != -1)
       {
            Console.WriteLine("Искомый индекс: " + res);
       }
       else
       {
            Console.WriteLine("Такого элемента нет в массиве");
       }

       Console.ReadKey();
 }