Глубокое погружение в основы алгоритмов поиска

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

  1. Последовательный поиск: список или массив просматривается последовательно, и каждый элемент проверяется.

например: линейный поиск

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

например: двоичный поиск

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

Линейный поиск

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

Как работает линейный поиск?

• Предположим, мы хотим найти значение x в массиве A.

Linear Search ( Array A, Value x)
Step 1: Set i to 0
Step 2: if i >= n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

Псевдокод

procedure linear_search (list, value)
   for each item in the list
      if match item == value
         return the item's location
      end if
   end for
end procedure

Код Java

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

Это алгоритм быстрого поиска со сложностью выполнения O (log N).

Алгоритм O (log N) считается высокоэффективным, поскольку отношение количества операций к размеру входных данных уменьшается и стремится к нулю при увеличении N. (N - размер входных данных в битах, необходимых для представления входных данных)

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

Как работает двоичный поиск?

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

Для работы двоичного поиска сначала необходимо отсортировать массив

Алгоритм

Предположим, мы хотим найти значение x в отсортированном массиве A.

Binary Search ( Array A, Value x)Step 1: Set R=0 and L=n-1
Step 2: if L > R then go to step 7
Step 3: Set m (the position of the middle element) to the floor of (L+R)/2
Step 4: If A[m] < x, set L to m+1 and go to Step 2
Step 5: If A[m] > x, set R to m-1 and go to Step 2
Step 6: Now A[m]= x, return m, and go to step 8
Step 7: Print element not found
Step 8: Exit

Псевдокод

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 0
   Set upperBound = n-1 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Код Java

Сегодня мы обсудили наиболее часто используемые методы поискового алгоритма. Давайте обсудим алгоритмы сортировки в следующей статье.

Ресурсы
Учебник
Гики для гиков
Википедия