Линейный и бинарный поиск в программе Python

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

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

• При линейном поиске вы начинаете с первого элемента и сравниваете каждый элемент с целевым значением, пока не найдете совпадение.
• Временная сложность: O(n).

Как это работает:

1. Начните с первого элемента массива.
2. Сравните целевое значение с текущим элементом.
3. Если оно соответствует, верните индекс.
4. Если нет, перейдите к следующему элементу.
5. Повторяйте шаги 2–4, пока не найдете цель или не достигнете конца массива.

Производительность:

• Временная сложность равна O(n), поскольку в худшем случае проверяется каждый элемент массива.
• Нет требований к сортировке массива.

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

• При двоичном поиске массив необходимо отсортировать. Вы неоднократно делите массив пополам, пока не будет найдено значение.
• Временная сложность: O(log n).

Как это работает:

1. Перед использованием двоичного поиска массив необходимо отсортировать.
2. Начните с установки двух указателей: одного в начале (слева) и одного в конце (справа) массива.
3. Найдите средний элемент.
4. Сравните средний элемент с целью.
5. Если оно соответствует, верните индекс.
6. Если цель больше среднего элемента, переместите левый указатель в середину + 1.
7. Если цель меньше среднего элемента, переместите правый указатель в середину — 1.
8. Повторяйте шаги 3–7, пока не найдете цель или перекрестие указателей (слева > справа).

Производительность:

• Временная сложность равна O(log n), поскольку она эффективно уменьшает пространство поиска вдвое с каждой итерацией.
• Требуется сортировка массива.

• Линейный поиск
• Пример
• Бинарный поиск
• Пример
• Реализация двоичного поиска без функции
• Пример
• Сравнение линейного и двоичного поиска

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

Вот пошаговое руководство по реализации алгоритма линейного поиска в Python:

def linear_search(arr, target):
    # Loop through each element in the array
    for index, element in enumerate(arr):
        # If the element matches the target, return the index
        if element == target:
            return index
    # If the loop finishes, the target was not found
    return -1

Пример

Давайте напишем программу на Python для линейного поиска, чтобы найти индекс целевого значения в массиве.

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Example array and target value
arr = [4, 2, 7, 1, 9, 3]
target = 7

# Call the linear_search function
index = linear_search(arr, target)

# Output the result
if index != -1:
    print(f"Element {target} found at index {index}")
else:
    print(f"Element {target} not found in the array")

Вы можете увидеть результат:

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

Вот пошаговое руководство по реализации двоичного поиска с помощью функции:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    # Continue the search while the left index is less than or equal to the right index
    while left <= right:
        mid =(left + right) // 2
        
        # Check if the target is present at mid
        if arr[mid] == target:
            return mid
        
        # If target is greater, ignore the left half
        elif arr[mid] < target:
            left = mid + 1
        
        # If target is smaller, ignore the right half
        else:
            right = mid - 1
    
    # If we reach here, the element was not present
    return -1

Пример

Давайте рассмотрим программу Python для реализации двоичного поиска с использованием приведенной выше функции.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid =(left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Example sorted array and target value
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6

# Call the binary_search function
index = binary_search(arr, target)

# Output the result
if index != -1:
    print(f"Element {target} found at index {index}")
else:
    print(f"Element {target} not found in the array")

Вы можете увидеть результат, как показано ниже:

Реализация двоичного поиска без функции

Вот как можно написать программу на Python для реализации двоичного поиска без использования функции.

Пример

# Example sorted array and target value
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6

# Set initial left and right indices
left, right = 0, len(arr) - 1

# Binary search without function
while left <= right:
    mid =(left + right) // 2
    
    # Check if target is present at mid
    if arr[mid] == target:
        print(f"Element {target} found at index {mid}")
        break
    
    # If target is greater, ignore the left half
    elif arr[mid] < target:
        left = mid + 1
    
    # If target is smaller, ignore the right half
    else:
        right = mid - 1
else:
    print(f"Element {target} not found in the array")

Вы можете увидеть результат ниже на скриншоте.

Сравнение линейного и двоичного поиска

Вот сравнение линейного поиска и двоичного поиска в Python в табличном формате: