#02 BINARY SEARCH

Qidirish algoritmlarini solishtiramiz

BINARY SEARCH

Tasavvur qiling siz Ingliz-O'zbek lug'atidan "Programming" so'zining tarjimasini qidirayapsiz. Siz ingliz alifbosidagi harflar tartibini bilasiz, shuning uchun lug'atni o'rtarog'idan ochib qaraysiz (P harfi lug'at o'rtasiga yaqin).

Yana bir misol, siz Googleda yangi [e-mail] akkauntini ochmoqchisiz. Google siz istagan akkaunt band yoki yo'qligini tekshirishi kerak (balki sizdan avval kimdur bu akkauntni band qilib bo'lgandur). Demak, Google o'zidagi akkauntlar ro'yxatidan siz kiritgan akkauntni qidirib ko'radi. Buning oson yo'li ro'yxat boshidan boshlab, siz istagan akkauntni barcha mavjud akkauntlar bilan solishtirib chiqish, lekin ro'yxat o'rtasidan boshlab tekshirish mantiqan to'g'ri bo'ladi.

Yuqoridagi usul (ro'yxat yoki lug'at o'rtasidan boshlash) Binary Search (ikkilik qidiruvi) deyiladi.

Binary Search ishlashi uchun ro'yxat tartiblangan bo'lishi shart!

NIMA UCHUN BINARY SEARCH?

Keling quyidagi miolni ko'ramiz: men 1 dan 100 gacha son o'yladim (deylik 30), siz bu sonni topishingiz kerak.

Agar ro'yxat boshidan qidiradigan bo'lsangiz, siz mendan "1 sonini o'yladingmi?" deb so'raysiz, men "Yo'q, kattaroq" deb javob qilaman. Siz endi "2 sonini o'yladingmi?" deb so'raysiz, men yana "Yo'q, kattaroq" deb javob qilaman va shu zaylda to 30 ga yetgunga qadar siz 30 marta "n-sonini o'yladingmi?" deb so'raysiz.

Bu Linear Search (chiziqli qidiruv) deyiladi.

Chiziqli qidiruv algoritmi:

def findNum(N=100):
    for n in range(1,100):
        ans = input(f"Siz {n}-o'yladingiz? (y/n)")
        if ans=='y':
            print("Yutdim!")
            return n

Bu usulning kamchiligi, agar men eng katta son, 100ni o'ylagan bo'lsam, siz bitta savolni 100 marta qayta so'raysiz. Algoritm ichidagi tsikl ham 100 marotaba takrorlanadi.

Yuqoridagi Google misolida oladigan bo'lsak, milliardlab foydalanuvchiga ega Google uchun chiziqli qidiruv milliardlab qadamdan iborat bo'ladi.

Keling endi Binary Search qanday ishlashini ko'ramiz.

Men yana 30 sonini o'yladim. Sizning birinchi savolingiz "50 sonini o'yladingmi?" bo'ladi. Men "Yo'q, kichikroq" deb javob qilaman va siz bemalol 50 dan katta sonlarni tashlab yuborasiz. 1-qadamdayoq ro'yxatimiz 2 barobar qisqardi va sizda 1-50 sonlar ro'yxati qoldi. Siz yana ro'yxat o'rtasidagi sonni so'raysiz: "25 sonini o'yladingmi?" bu safar men "Yo'q, kattaroq" deb javob qilaman, va bu safar siz ro'yxatning 1-yarmini tashlab yuborasiz (1-25) va ikkinchi yarmining (25-50) o'rtasidan so'raysiz. Va hokazo to to'g'ri sonni topgunga qadar shu zaylda davom etasiz va 30 sonini 6-qadamda topasiz.

Endi tasavur qiling, siz 40000 so'zdan iborat lug'atdan biror so'zni qidirayapsiz. Agar soz lug'at so'ngida bo'lsa (eng so'nngi so'z) chiziqli qidiruv 40000 qadamdan, binary search esa 15 qadamdan iborat bo'ladi xolos.

Agar lug'at tarkibini ikki barobar ko'paytrisak (80000) so'z, chiziqli qidiruv qadamlari ham 2 barobar oshadi, binary search esa bor yo'gi 1 qadamga (16 qadam) oshadi xolos.

QADAMLAR SONI

Umuman olganda N uzunlikdagi ro'yxat uchun, chiziqli qidiruvda maksimal qadamlar soni ro'yxat uzunligiga (N), binary searchda esa $log_2(N)$ ga teng bo'ladi.

Logarifmlarni bir takrorlab olsak, logarifm bu darajaning aksi:

Eksponenta	Logarifm
$2^2=4$	$log_2(4)=2$
$2^3=8$	$log_2(8)=3$
$2^4=16$	$log_2(16)=4$

Demak, agar ro'yxatimiz 2048 elementdan iborat bo'lsa, Binary Searh qadamlari soni $log_2(2048)=11$ ga teng bo'ladi.

AMALIYOT

Linear va Binary search uchun algoritm yozing.

KOD

def binary_search(list, item):
    low = 0
    high = len(list)-1
    while low <= high:
        mid = (low + high)//2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

myList = [1,3,4,6,7,8,10,12,23]
print(binary_search(myList,6))