10 класс Информатика ГДЗ учебник Поляков 2 часть Параграф 65

10 класс Информатика ГДЗ учебник Поляков 2 часть Параграф 65 Двоичный поиск

Стр.235.

1. Алгоритм называется двоичным, потому что на каждом шаге зона поиска делится на две равные части. В результате каждый раз объем данных, в котором продолжается поиск, уменьшается вдвое.

2. Примером использования двоичного поиска в жизни является поиск слова в словаре: сначала мы открываем словарь примерно на середине и проверяем, в какой половине находится искомое слово, затем аналогично поступаем с оставшейся половиной и так далее, пока не найдем нужное слово.

Еще один пример — поиск числа в телефонном справочнике, отсортированном по фамилиям. Мы сначала проверяем середину справочника, затем продолжаем поиск в соответствующей половине и так далее.

3. Количество шагов при двоичном поиске можно приблизительно оценить как логарифм от числа элементов массива по основанию 2. Например, для массива из 1024 элементов потребуется примерно 10 шагов (так как $2^{10} = 1024$ ).

4. Достоинства линейного поиска:

Простота реализации.
Работает на неотсортированных массивах.

Недостатки линейного поиска:

Время выполнения пропорционально числу элементов (O(N)).

Достоинства двоичного поиска:

Значительно быстрее для больших отсортированных массивов (O(log N)).

Недостатки двоичного поиска:

Требуется предварительная сортировка массива, что может занять значительное время.
Работает только на отсортированных массивах.

Проект

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

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

import time
import random

# Линейный поиск
def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

# Двоичный поиск
def binary_search(arr, x):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Генерация отсортированного списка случайных чисел
def generate_sorted_list(size):
    return sorted(random.randint(1, 100000) for _ in range(size))

# Измерение времени выполнения функции
def measure_time(search_function, arr, x):
    start_time = time.time()
    result = search_function(arr, x)
    end_time = time.time()
    return end_time - start_time, result

def main():
    sizes = [1000, 10000, 100000]
    x = 50000  # Искомое значение

    for size in sizes:
        arr = generate_sorted_list(size)
        print(f"\nРазмер массива: {size}")

        lin_time, lin_result = measure_time(linear_search, arr, x)
        print(f"Линейный поиск: {lin_time:.6f} секунд, результат: {lin_result}")

        bin_time, bin_result = measure_time(binary_search, arr, x)
        print(f"Двоичный поиск: {bin_time:.6f} секунд, результат: {bin_result}")

if __name__ == "__main__":
    main()

import time

import random

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

def linear_search(arr, x):

for i in range(len(arr)):

if arr[i] == x:

return i

return -1

# Двоичный поиск

def binary_search(arr, x):

left, right = 0, len(arr) - 1

while left <= right:

mid = (left + right) // 2

if arr[mid] == x:

return mid

elif arr[mid] < x:

left = mid + 1

else:

right = mid - 1

return -1

# Генерация отсортированного списка случайных чисел

def generate_sorted_list(size):

return sorted(random.randint(1, 100000) for _ in range(size))

# Измерение времени выполнения функции

def measure_time(search_function, arr, x):

start_time = time.time()

result = search_function(arr, x)

end_time = time.time()

return end_time - start_time, result

def main():

sizes = [1000, 10000, 100000]

x = 50000 # Искомое значение

for size in sizes:

arr = generate_sorted_list(size)

print(f"\nРазмер массива: {size}")

lin_time, lin_result = measure_time(linear_search, arr, x)

print(f"Линейный поиск: {lin_time:.6f} секунд, результат: {lin_result}")

bin_time, bin_result = measure_time(binary_search, arr, x)

print(f"Двоичный поиск: {bin_time:.6f} секунд, результат: {bin_result}")

if __name__ == "__main__":

main()

Объяснение

linear_search(arr, x): Реализует линейный поиск элемента в массиве.
binary_search(arr, x): Реализует двоичный поиск элемента в массиве.
generate_sorted_list(size): Генерирует отсортированный список случайных чисел заданного размера.
measure_time(search_function, arr, x): Измеряет время выполнения функции поиска и возвращает время и результат поиска.
main(): Основная функция для выполнения эксперимента. Тестирует оба метода поиска с массивами разного размера и выводит время выполнения и результат.

Запустите этот код, чтобы увидеть, как линейный и двоичный поиск работают с массивами размером 1000, 10000 и 100000 элементов. Это поможет вам понять эффективность каждого метода на практике.

10 класс Информатика ГДЗ учебник Поляков 2 часть Параграф 65

Проект

Объяснение

Добавить комментарий Отменить ответ