Qidiruv algoritmlari

def chiziqli_qidir(massiv, qidirilayotgan):
    """Ketma-ket qidiruv. O(n). Tartiblangan bo'lishi shart emas."""
    for indeks, element in enumerate(massiv):
        if element == qidirilayotgan:
            return indeks
    return -1


baholar = [85, 92, 78, 95, 88]
print(chiziqli_qidir(baholar, 95))
print(chiziqli_qidir(baholar, 70))

def ikkilik_qidir(massiv, qidirilayotgan):
    """Ikkilik qidiruv. O(log n). Massiv TARTIBLANGAN bo'lishi SHART."""
    chap, ong = 0, len(massiv) - 1

    while chap <= ong:
        orta = (chap + ong) // 2

        if massiv[orta] == qidirilayotgan:
            return orta
        if massiv[orta] < qidirilayotgan:
            chap = orta + 1            # o'ng yarimda qidiramiz
        else:
            ong = orta - 1             # chap yarimda qidiramiz

    return -1


sonlar = [2, 7, 11, 15, 19, 23, 31]
print(ikkilik_qidir(sonlar, 23))
print(ikkilik_qidir(sonlar, 20))

def ikkilik_qidir_rekursiv(massiv, qidirilayotgan, chap=0, ong=None):
    """Rekursiv ikkilik qidiruv."""
    if ong is None:
        ong = len(massiv) - 1

    if chap > ong:
        return -1

    orta = (chap + ong) // 2

    if massiv[orta] == qidirilayotgan:
        return orta
    if massiv[orta] < qidirilayotgan:
        return ikkilik_qidir_rekursiv(massiv, qidirilayotgan, orta + 1, ong)
    return ikkilik_qidir_rekursiv(massiv, qidirilayotgan, chap, orta - 1)


print(ikkilik_qidir_rekursiv([2, 7, 11, 15, 19, 23, 31], 11))

import time

N = 10_000_000
katta_massiv = list(range(N))
qidirilayotgan = N - 1              # eng yomon holat

boshlanish = time.perf_counter()
chiziqli_qidir(katta_massiv, qidirilayotgan)
chiziqli_vaqt = time.perf_counter() - boshlanish

boshlanish = time.perf_counter()
ikkilik_qidir(katta_massiv, qidirilayotgan)
ikkilik_vaqt = time.perf_counter() - boshlanish

print(f"Chiziqli qidiruv: {chiziqli_vaqt:.6f} soniya")
print(f"Ikkilik qidiruv:  {ikkilik_vaqt:.6f} soniya")
print(f"Farq:             {chiziqli_vaqt / ikkilik_vaqt:,.0f} barobar")

import bisect

sonlar = [2, 7, 11, 15, 19, 23, 31]

# Element qayerga qo'yilishi kerakligini topadi
print(bisect.bisect_left(sonlar, 15))     # 15 ning o'zi turgan joy
print(bisect.bisect_right(sonlar, 15))    # 15 dan keyingi joy
print(bisect.bisect_left(sonlar, 20))     # 20 qayerga qo'yilishi kerak

# Tartibni saqlagan holda qo'shish
bisect.insort(sonlar, 20)
print(sonlar)

import bisect


def bormi(massiv, qiymat):
    """Element mavjudligini tekshiradi. O(log n)."""
    i = bisect.bisect_left(massiv, qiymat)
    return i < len(massiv) and massiv[i] == qiymat


def nechta_marta(massiv, qiymat):
    """Element necha marta uchrashini sanaydi. O(log n)."""
    chap = bisect.bisect_left(massiv, qiymat)
    ong = bisect.bisect_right(massiv, qiymat)
    return ong - chap


def oraliqda_nechta(massiv, past, yuqori):
    """Berilgan oraliqdagi elementlar sonini qaytaradi. O(log n)."""
    return bisect.bisect_right(massiv, yuqori) - bisect.bisect_left(massiv, past)


baholar = [60, 70, 78, 85, 85, 85, 92, 95, 100]

print("85 bormi:            ", bormi(baholar, 85))
print("85 necha marta:      ", nechta_marta(baholar, 85))
print("80-95 oralig'ida:    ", oraliqda_nechta(baholar, 80, 95), "ta")

import bisect

CHEGARALAR = [60, 70, 80, 90]
HARFLAR = ["F", "D", "C", "B", "A"]


def harfli_baho(ball):
    """if/elif zanjiri o'rniga O(log n) qidiruv."""
    return HARFLAR[bisect.bisect_right(CHEGARALAR, ball)]


for ball in [45, 65, 75, 85, 95, 100]:
    print(f"{ball:>4} ball -> {harfli_baho(ball)}")

def birinchi_uchrashi(massiv, qiymat):
    """Takrorlanuvchi qiymatning birinchi indeksini topadi."""
    chap, ong = 0, len(massiv) - 1
    natija = -1

    while chap <= ong:
        orta = (chap + ong) // 2
        if massiv[orta] == qiymat:
            natija = orta
            ong = orta - 1              # chapda yana bormi?
        elif massiv[orta] < qiymat:
            chap = orta + 1
        else:
            ong = orta - 1

    return natija


def oxirgi_uchrashi(massiv, qiymat):
    chap, ong = 0, len(massiv) - 1
    natija = -1

    while chap <= ong:
        orta = (chap + ong) // 2
        if massiv[orta] == qiymat:
            natija = orta
            chap = orta + 1             # o'ngda yana bormi?
        elif massiv[orta] < qiymat:
            chap = orta + 1
        else:
            ong = orta - 1

    return natija


baholar = [60, 70, 85, 85, 85, 92, 95]
print("Birinchi 85:", birinchi_uchrashi(baholar, 85))
print("Oxirgi 85:  ", oxirgi_uchrashi(baholar, 85))

def kvadrat_ildiz(son, aniqlik=1e-9):
    """Ikkilik qidiruv bilan kvadrat ildiz topish."""
    if son < 0:
        raise ValueError("Manfiy sondan ildiz chiqarilmaydi")
    if son == 0:
        return 0.0

    chap, ong = 0.0, max(1.0, son)

    while ong - chap > aniqlik:
        orta = (chap + ong) / 2
        if orta * orta < son:
            chap = orta
        else:
            ong = orta

    return (chap + ong) / 2


print(f"{kvadrat_ildiz(144):.6f}")
print(f"{kvadrat_ildiz(2):.6f}")

def eng_kam_javon(kitoblar, javon_uzunligi):
    """Berilgan uzunlikdagi javonlarga necha marta bo'lish kerakligini hisoblaydi."""
    javonlar = 1
    joriy = 0
    for kitob in kitoblar:
        if joriy + kitob > javon_uzunligi:
            javonlar += 1
            joriy = kitob
        else:
            joriy += kitob
    return javonlar


def minimal_javon_uzunligi(kitoblar, javonlar_soni):
    """Kitoblarni k ta javonga sig'dirish uchun minimal javon uzunligini topadi."""
    chap = max(kitoblar)                 # kamida eng katta kitob sig'ishi kerak
    ong = sum(kitoblar)                  # ko'pi bilan hammasi bitta javonda

    while chap < ong:
        orta = (chap + ong) // 2
        if eng_kam_javon(kitoblar, orta) <= javonlar_soni:
            ong = orta                   # kichikroq javon ham yetadimi?
        else:
            chap = orta + 1

    return chap


kitoblar = [30, 20, 45, 15, 25, 40, 35]
for javonlar in [2, 3, 4]:
    uzunlik = minimal_javon_uzunligi(kitoblar, javonlar)
    print(f"{javonlar} ta javon uchun minimal uzunlik: {uzunlik} sm")