Algorithms SkillFactory

Appearance

Задача поиска. Абстракция поиска. Последовательный поиск. Бинарный поиск. Распределяющий поиск. ​

Определение ​

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

Абстракция поиска представляет собой общий концепт, описывающий процесс нахождения элемента в коллекции данных. Это включает в себя определение:

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

Виды поисков ​

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

  • Время выполнения 𝑂(𝑛)
  • Подходит для неотсортированных и небольших массивов.
python
def linearSearch(arr, x):  
    for i in range(len(arr)):  
        if arr[i] == x:  
            return i

Бинарный поиск — это более эффективный метод поиска, который используется для отсортированных массивов. Алгоритм работает по принципу «разделяй и властвуй»: на каждом шаге он делит массив пополам и сравнивает средний элемент с искомым значением, отбрасывая ту половину, в которой элемент не может находиться.

  • Время выполнения 𝑂(log𝑛).
  • Требует отсортированного массива.
python
def binarySearchReq(arr, x, left, right):  
    if left > right:  
        return -1  
	  
    mid = (left + right) // 2  
	  
    if arr[mid] > x:  
        return binarySearchReq(arr, x, left, mid - 1)  
    elif arr[mid] < x:  
        return binarySearchReq(arr, x, mid + 1, right)  
	  
    return mid  
  
def binarySearch(arr, x):  
    left = 0  
    right = len(arr) - 1  
	  
    while left <= right:  
        mid = (left + right) // 2  
        if arr[mid] < x:  
            left = mid + 1  
        elif arr[mid] > x:  
            right = mid - 1  
        else:  
            return mid  
	  
    return -1

Распределяющий поиск (интерполяционный поиск) — это метод, аналогичный бинарному поиску, но вместо деления массива пополам, он использует линейную интерполяцию для оценки позиции искомого элемента. Этот метод эффективен, когда элементы массива равномерно распределены.

  • Эффективен для равномерно распределенных данных.
  • Время выполнения 𝑂(loglog𝑛) в лучшем случае.
python
def interpolationSearch(arr, x):  
    left = 0  
    right = len(arr) - 1  
	  
    while left < right and arr[left] <= x <= arr[right]:  
        pos = left
	        + ((right - left) // (arr[right] - arr[left])
	        * (x - arr[left]))  
	  
        if arr[pos] < x:  
            left = pos + 1  
        elif arr[pos] > x:  
            right = pos - 1  
        else:  
            return pos  
	  
    if left == right and arr[left] == x:  
        return left  
    return -1