Глубокое погружение в основы алгоритмов поиска
Основная цель поисковых алгоритмов - проверить элемент или извлечь его из любой структуры данных. Эти поисковые алгоритмы подразделяются на две разные части, как правило, в зависимости от типа поиска.
- Последовательный поиск: список или массив просматривается последовательно, и каждый элемент проверяется.
например: линейный поиск
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
Сегодня мы обсудили наиболее часто используемые методы поискового алгоритма. Давайте обсудим алгоритмы сортировки в следующей статье.
Ресурсы
Учебник
Гики для гиков
Википедия