Задача «Линейный и бинарный поиск»

Постановка задачи

Задан массив A из N элементов одного типа. Это могут быть числа, строки, структуры. Число N может быть достаточно велико (например, сотни миллионов).

Требуется найти расположение заданного элемента в массиве по запросу b, то есть найти такое k, для которого A[k]=b.  Массив A может быть неупорядоченным, либо упорядоченным по возрастанию/убыванию значений элементов.

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

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

Эффективность алгоритма поиска

Поиск при работе с данными (особенно с базами данных) является самой массовой (часто используемой) операцией.

Критерием эффективности алгоритма является  количество операций сравнения при циклическом поиске заданного элемента. Замедление поиска заметно только при больших значениях N. Поэтому, если ваш тест содержит 10, 100 или 1000 элементов, то скорее всего поиск займет миллисекунды.

Мы можем теоретически оценить зависимость количество операций сравнения, равно как и время поиска T в зависимости от N, а затем проверить это с секундомером, запустив нашу программу.

Алгоритм линейного поиска

В цикле по всем элементам массива проверяем условие остановки поиска A[k]=b. При выполнении на k-м элементе этого условия осуществляется досрочный выход из цикла. Если местоположение искомого элемента в массиве равновероятно (в начале, в конце или середине), то математическое ожидание T ~ N/2 (теоретическая оценка).

Алгоритм бинарного поиска

Алгоритм не применим к неупорядоченному массиву (вероятность получения результата крайне мала). Однако на упорядоченном массиве он обеспечивает более быстрое получение результата: T ~ log₂N (теоретическая верхняя оценка).

Пусть для примера N=10⁹, тогда для линейного поиска T ~ 500000000 операций, а для бинарного поиска T ~ 30. Отметим, что обязательным условием достижение результата при бинарном поиске является упорядоченность массива.

Идея алгоритма очень проста. Выбирается элемент в середине массива. Если он больше b, то следует искать его во второй половине массива, иначе — первой. То есть исходная последовательность делится пополам, потом выбранная подпоследовательность делится снова пополам и так далее. Этот метод («метод дихотомии») поэтому имеет логарифмическую (по основанию 2) зависимость времени вычислений от числа элементов.

Программная реализация

В классе Program объявим три объекта:
static int [] a = new int[1000];     // массив целых чисел
static int counter;    // счетчик числа сравнений
static int n;                // число элементов
Переменная counter нам будет полезна при анализе эффективности алгоритмов.

Кроме метода Main() добавим в класс Program пять методов:
static void arr1Gen()  // Генератор упорядоченного по возрастанию массива
static void arr2Gen()  // Генератор массива случайных чисел
static int linePoisk(int b)  // Линейный поиск
static int binPoisk(int b)  // Бинарный поиск
static void comparison2()  // Сравнение двух видов поиска

Примечание. В генераторах массивов используется объект класса Random для генерации элементов массива, причем в первом случае массив гарантированно упорядочен по возрастанию, во втором случае этого не будет.

Код приложения представлен ниже:

// Линейный и бинарный поиск
using System;
namespace поиск
{
class Program
{
  static int [] a = new int[1000];
  static int counter;  // счетчик числа сравнений
  static int n;   // число элементов
  static void Main(string[] args)
  {
     Console.Write("Ввести количество элементов: ");
     n = Convert.ToInt32(Console.ReadLine());
     // Упорядоченный по возрастанию массив       
     Console.WriteLine("\nПоиск в упорядоченном по возрастанию массиве");
     arr1Gen();
     comparison2();
     // Неупорядоченный массив
     Console.WriteLine("\nПоиск в неупорядоченном массиве");
     arr2Gen();
     comparison2();
     Console.ReadKey();
  }
// Сравнение двух видов поиска
  static void comparison2()
  {  
     // Предмет поиска      
     Console.Write("Ввести элемент поиска: ");
     int b = Convert.ToInt32(Console.ReadLine());
     // Линейный поиск
     int k = linePoisk(b);
     Console.WriteLine("Линейный поиск:");
     if (k > -1)
        Console.WriteLine("Номер элемента = {0}, число сравнений внутри цикла = {1}", k, counter);
     else
         Console.WriteLine("нет заданного элемента, число сравнений внутри цикла = {0}", counter);
     // Бинарный поиск        
     k = binPoisk(b);
     Console.WriteLine("Бинарный поиск:");
     if (k > -1)
         Console.WriteLine("Номер элемента = {0}, число сравнений внутри цикла = {1}", k, counter);
     else
         Console.WriteLine("нет заданного элемента, число сравнений внутри цикла = {0}", counter);
  }
// Генератор упорядоченного по возрастанию массива
  static void arr1Gen()
  {
     Random ran = new Random();
     a[0] = ran.Next(1, 6);
     Console.Write("  {0}", a[0]);
     for (int i = 1; i < n; i++)
     {
        a[i] = a[i - 1] + ran.Next(1, 6);
        Console.Write("  {0}", a[i]);
     }
     Console.WriteLine();
  }
// Генератор массива случайных чисел
  static void arr2Gen()
  {
     Random ran = new Random();
     for (int i = 0; i < n; i++)
     {
        a[i] = ran.Next(1, 100);
        Console.Write("  {0}", a[i]);
     }
     Console.WriteLine();
  }
  // Линейный поиск     
  static int linePoisk(int b)
  {
     int k = -1;
     counter = 0;
     for (int i = 0; i < n; i++)
     {
         counter++;
        if (a[i] == b) { k = i; break; };
     }
     return k;
  }
  // Бинарный поиск
  static int binPoisk(int b)
  {
     int k;   // с
     int L = 0;        // левая граница
     int R = n - 1;    // правая граница
     k = (R + L) / 2;
     counter = 0;
     while (L<R-1)
     {
        counter++;
        k = (R + L) / 2;
        if (a[k] == b)         
           return k; // Вместо break;, см.комментарий
        counter++;
        if (a[k] < b)
           L = k;
        else
           R = k;
     }
     if (a[k] != b)
     {
        if (a[L] == b)
           k = L;
        else
        {
           if (a[R] == b)
              k = R;
           else
              k = -1;
        };
     }
     return k; 
  }
 } 
}

Результат:

Примечания

В методах поиска оператор break; используется для досрочного выхода из цикла. Счетчик counter увеличивается только внутри циклов.  В примере выбрано N=40 для наглядности.

Обратите внимание на критерий эффективности (число сравнений) для двух видов поиска в упорядоченном по возрастанию массиве и сбой алгоритма бинарного поиска в неупорядоченном массиве.

Самостоятельные исследования эффективности алгоритмов поиска

Исследуйте с секундомером работу программы при больших N (до 400000000), чуть изменив программу — удалив вывод элементов на консоль.

Следующая задача — Пифагоровы треугольники.

---

NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.

---

Помощь проекту: