Алгоритми пошуку
Алгоритм пошуку — алгоритм, який вирішує задачу пошуку, тобто, знаходить інформацію, яка зберігається в певній структурі даних.
Алгоритми пошуку класифікуються на основі їх механізму пошуку:
Лінійний пошук
Лінійний пошук працює достатньо повільно, але на практиці часто зустрічається. Алгоритм лінійного пошуку порівнює кожний елемент в структурі даних зі значенням котре потрібно знайти.
Задача
Знайти елемент списку, рівний X, або встановити, що його немає.
Для довільного списку використаємо лінійний пошук (перебір)
n = int(input())
x = int(input())
a = list(map(int,input().split()))
nx=0 # номер потрібного елемента списку, поки не знайшли
for i in range(n): # цикл по усім елементам
if a[i] == x: # якщо знайшли, то
nx=i # запам'ятали
break # вийшли з циклу
if nx<0:
print('No')
else:
print(nx+1)
Бінарний пошук
Існує також бінарний пошук, або половинно-інтервальний пошук, однак він працює лише з відсортованими елементами, один з найшвидших алгоритмів, який повторно порівнює пошуковий елемент з центральним елементом заданої структури, якщо знайшов то кінець, якщо ні, то порівнює елементи та продовжує пошук в лівій чи правій частині структури даних поки не знайде потрібний.
Алгоритм
1.Вибрати середній елемент A[c] і порівняти з X.
2.Якщо X = A[c], знайшли (вихід).
3.Якщо X < A[c], шукати дальше в першій половині.
4.Якщо X > A[c], шукати дальше в другій половині.
Задача
Знайти елемент списку, рівний X, або встановити, що його немає.
n = int(input())
x = int(input())
a = list(map(int,input().split()))
nX = 0
L = 1
R = n #межі: шукаємо від A[1] до A[N]
while R >= L:
c=(R + L)//2 #номер середнього елемента
if x == a[c]:
nX=c
R=L-1
break
#зсуваємо межі
if x < a[c]:
R=c - 1
if x > a[c]:
L= c + 1
if nX < 0:
print('Не знайшли...')
else:
print('A[', nX+1, ']=', x)