Учебники

Python — Алгоритмы поиска

Декабрь 19, 2018

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

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

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


def linear_search(values, search_for):
    search_at = 0
    search_res = False

# Match the value with each data element	
    while search_at < len(values) and search_res is False:
        if values[search_at] == search_for:
            search_res = True
        else:
            search_at = search_at + 1

    return search_res

l = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(l, 12))
print(linear_search(l, 91))

Когда приведенный выше код выполняется, он дает следующий результат — 

True
False

Интерполяционный поиск

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

Существует специальная формула для расчета средней позиции, которая указана в программе ниже. 


def intpolsearch(values,x ):
    idx0 = 0
    idxn = (len(values) - 1)

    while idx0 <= idxn and x >= values[idx0] and x <= values[idxn]:

# Find the mid point
	mid = idx0 +\
               int(((float(idxn - idx0)/( values[idxn] - values[idx0]))
                    * ( x - values[idx0])))

# Compare the value at mid point with search value 
        if values[mid] == x:
            return "Found "+str(x)+" at index "+str(mid)

        if values[mid] < x:
            idx0 = mid + 1
    return "Searched element not in the list"


l = [2, 6, 11, 19, 27, 31, 45, 121]
print(intpolsearch(l, 2))

Когда приведенный выше код выполняется, он дает следующий результат —

71
Share: