2. Qidiruv va ma’lumot tuzilmasini tanlash

Chiziqli qidiruv

Eng sodda usul — hammasini ko‘rib chiqish:

for i, x in enumerate(a):
    if x == izlangan:
        print(i)
        break

Bu O(n). Bitta qidiruv uchun yaxshi, lekin q ta so‘rov bo‘lsa
O(n·q) chiqadi: n = q = 200 000 bo‘lsa, 4·10¹⁰ amal — ulgurmaydi.

To‘g‘ri tuzilma masalani hal qiladi

# Sekin: har so‘rovda butun ro‘yxat ko‘riladi
if x in royxat:        # O(n)

# Tez: bir marta to‘plam quriladi, keyin har so‘rov deyarli bepul
toplam = set(royxat)   # O(n) — bir marta
if x in toplam:        # O(1) — har so‘rovda

Sanash masalalari

«Nechta har xil son bor», «qaysi element eng ko‘p uchraydi»,
«ikkita bir xil son bormi» — bularning hammasi lug‘at yoki to‘plam
bilan bir o‘tishda yechiladi:

sanoq = {}
for x in a:
    sanoq[x] = sanoq.get(x, 0) + 1

Ikkita son yig‘indisi

Klassik masala: massivda yig‘indisi S ga teng ikkita son bormi?

Sodda yechim — ichma-ich ikkita sikl, O(n²). Lug‘at bilan esa bir
o‘tishda:

korilgan = set()
for x in a:
    if S - x in korilgan:
        print("bor")
        break
    korilgan.add(x)

Bu O(n). Fikr oddiy: har bir son uchun «juftim oldin uchraganmi?» deb
so‘raymiz.