linear and binary search

list.py

import random
import time

# розмір списку
size = 50000

# список цілих чисел
ar = [random.randint(0, 9999) for _ in range(size)]

# виведення списку
print(", ".join(map(str, ar[:50])), "\n") # виводимо перші 50 елементів для зручності

# значення для пошуку в списку
value_to_find = 777

##################################################################
# лінійний пошук
##################################################################
linear_iteration_count = 0
linear_index = -1

start_time = time.perf_counter()

for i in range(size):
    linear_iteration_count += 1
    if ar[i] == value_to_find:
        linear_index = i
        break

end_time = time.perf_counter()

work_time = (end_time - start_time) * 1000.0  # перетворюємо в мілісекунди

print(f"Значення знайдено за індексом: {linear_index}")
print(f"Кількість ітерацій лінійного пошуку: {linear_iteration_count}")
print(f"Час роботи лінійного пошуку: {work_time:.6f} мс.")
print("\n////////////////////////////////////////\n")

##################################################################
# бінарний пошук
##################################################################
binary_iteration_count = 0
binary_index = -1

# сортуємо список
ar.sort()

# виведення відсортованого списку - перші 50 елементів для зручності
print(", ".join(map(str, ar[:50])))
print("\n")

start_time = time.perf_counter()

L, R = 0, size - 1  # ліва та права межі
while L <= R:
    binary_iteration_count += 1
    M = L + (R - L) // 2  # обчислюємо індекс елемента по середині списку
    if ar[M] > value_to_find:
        R = M - 1
    elif ar[M] < value_to_find:
        L = M + 1
    else:
        binary_index = M
        break

end_time = time.perf_counter()

work_time = (end_time - start_time) * 1000.0

print(f"Значення знайдено за індексом: {binary_index}")
print(f"Кількість ітерацій бінарного пошуку: {binary_iteration_count}")
print(f"Час роботи бінарного пошуку: {work_time:.6f} мс.")