Python'da binary search 101: amalga oshirish va qo'llanish holatlari

Python'da binary search yordamida qidiruv tezligini oshiring. Python'da binary search nima ekanini va uni qanday amalga oshirishni o'rganing.

Sekin qidiruv bilan tez qidiruv o'rtasidagi farq ko'pincha siz tanlagan algoritmga borib taqaladi. Yaxshi qidiruv algoritmi, masalan, binary search, butun list'ni ko'zdan kechirib chiqmasdan ma'lumotlarni tezroq topishga yordam beradi. Binary search — computer science'dagi asosiy qidiruv algoritmlaridan biri bo'lib, u maqsadli qiymatni topish uchun zarur bo'lgan taqqoslashlar sonini minimal darajaga tushiradi. Ushbu qidiruv algoritmini tushunish Python dasturchilariga sort qilingan ma'lumotlar tuzilmalari bilan yaxshiroq ishlashga yordam beradi.

Python binary search'ni turli usullarda amalga oshirish imkonini beradi. U loop'lar yoki recursion yordamida binary search'ni o'zingiz yozishingizga imkon beradi. Agar uni o'zingiz yozishni istamasangiz, Python'da bu ishni siz uchun bajaradigan bisect moduli kabi built-in funksiyalar mavjud. Uni o'zingiz yozasizmi yoki built-in funksiyadan foydalanasizmi, binary search uchun sort qilingan list kerak bo'ladi. Ma'lumotlaringizni sort qilsangiz, qidiruvlar tezroq bo'ladi, qaysi usuldan foydalanishni bilish esa muhim.

Sort qilingan list'larda qidirishni bilish — dasturchi sifatidagi butun faoliyatingiz davomida o'zini oqlaydigan ko'nikma. U kod yozayotganda tezlik va muammolarni hal qilish haqida qanday fikrlashingizni yaxshilaydi. Binary search'ni o'rganish sizni texnik ish suhbatlariga ham tayyorlaydi. Intervyu oluvchilar kod yozish va muammolarni hal qilish ko'nikmalaringizni baholash uchun binary search bo'yicha savollardan foydalanadi.

Ushbu qo'llanmada siz Python'dagi binary search haqida bilishingiz kerak bo'lgan hamma narsani o'rganasiz. So'ngra uni Python'da qanday amalga oshirish va qachon ishlatish kerakligini ko'rasiz. O'rganish kerak bo'lgan Python asoslari va algoritmlarini batafsil ko'rish uchun Python roadmap'ga nazar tashlang.

Python'da binary search nima?

Python'dagi binary search — sort qilingan massiv yoki list ichidan maqsadli qiymatning index'ini topadigan samarali qidiruv algoritmi. U list ichidan muayyan elementni qidirish uchun divide-and-conquer yondashuvidan foydalanadi. Har bir qadamda qidiruv oralig'ini ikkiga bo'lgani sababli, u har bir elementni birma-bir tekshirishdan ancha tezroq ishlaydi.

Binary search ishni sort qilingan list'ingizdagi o'rta elementni tekshirishdan boshlaydi. Agar o'rta element maqsadli qiymatingizga mos kelsa, qidiruv yakunlanadi. Agar maqsadli qiymat o'rta elementdan kichik bo'lsa, qidiruv chap yarmida davom etadi. Agar maqsadli qiymat kattaroq bo'lsa, qidiruv algoritmi chap yarmini e'tiborsiz qoldiradi va o'ng yarmida qidiradi. Bu jarayon maqsadli qiymatni topguningizcha yoki tekshiriladigan elementlar tugaguncha davom etadi.

Binary search qanday ishlashini yaxshiroq tushunish uchun 13 maqsadli sonini topish misolini ko'rib chiqamiz:

numbers = [2, 5, 8, 12, 13, 17, 20, 23, 26] 
target = 13
# Indices: 0 1 2 3 4 5 6 7 8

Yuqoridagi misoldagi sort qilingan massiv, [2, 5, 8, 12, 13, 17, 20, 23, 26], 9 ta elementdan iborat bo'lib, uning index'lari 0 dan 8 gacha. Binary search algoritmi quyidagi qadamlarni bajaradi:

1-qadam: O'rta index'dagi (4) elementni tekshiring, uning qiymati (13). U siz qidirayotgan maqsadli qiymatga (13) mos kelgani uchun qidiruv to'xtaydi. Shundan so'ng qidiruv algoritmi maqsadli qiymatning index'i sifatida (4) index'ni qaytaradi.

Xuddi shu sort qilingan massivdan foydalanib, maqsadli qiymat o'rta index'da bo'lmagan holatda 17 ni qidirib ko'ramiz:

1-qadam: O'rta index — 4, o'rta qiymat — 13. 17 > 13 bo'lgani uchun binary search algoritmi chap yarmini (0-4 index'lar: 2, 5, 8, 12, 13) e'tiborsiz qoldiradi. Lekin o'ng yarmida qidirishni davom ettiradi.
2-qadam: Qolgan sort qilingan massiv [17, 20, 23, 26]'da yangi o'rta index — 6, o'rta qiymat — 20. 17 < 20 bo'lgani uchun binary search algoritmi o'ng tomonni e'tiborsiz qoldiradi va chap tomonni saqlab qoladi.
3-qadam: Bu bosqichda sort qilingan massivingizda faqat [17] qoladi. Shundan so'ng binary search algoritmi maqsadli qiymatning index'i sifatida 5 index'ni qaytaradi.

Binary search elementlarga ularning index'i orqali to'g'ridan-to'g'ri murojaat qilishni talab qiladi. U linked list'lar kabi ma'lumotlar tuzilmalari bilan yaxshi ishlamaydi, chunki ular istalgan pozitsiyaga to'g'ridan-to'g'ri murojaat qilishni qo'llab-quvvatlamaydi. Siz har bir node'ni birma-bir qayta ishlashingiz kerak bo'ladi, bu esa binary search'ning tezlikdagi ustunligini yo'qqa chiqaradi.

Binary search'ni qo'llashdan oldin ma'lumotlaringizni o'sish yoki kamayish tartibida sort qilishni unutmang. Agar bu qadamni o'tkazib yuborib, sort qilinmagan ma'lumotlarda binary search'ni ishga tushirsangiz, algoritm to'g'ri ishlamaydi. U noto'g'ri natijalar berishi yoki maqsadli qiymatingizni butunlay o'tkazib yuborishi mumkin.

Yuqoridagi misolda binary search to'qqizta element orasidan maqsadli qiymatni bor-yo'g'i uchta taqqoslashda topdi, chunki siz ma'lumotlaringizni sort qilgan edingiz. Sort qilinmaganida esa linear search kabi boshqa qidiruv algoritmlaridan foydalanishingiz kerak bo'lardi, ular maqsadli qiymatni topish uchun to'qqiztagacha tekshiruv talab qilishi mumkin.

Binary search va linear search algoritmi

Binary search samarali, lekin har doim ham eng yaxshi tanlov emas. Ba'zi vaziyatlarda linear search algoritmi kabi soddaroq usul ko'proq mos keladi. Ikkala algoritmni bilish loyihalaringiz uchun to'g'risini tanlashga yordam beradi.

Linear search algoritmi list yoki massivdagi elementlarni topishda oddiy yondashuvdan foydalanadi. U kerakli qiymatni topguningizcha yoki oxirgi elementga yetguningizcha list bo'ylab qadam-baqadam o'tadi. Bu birma-bir tekshirish yondashuvi ishlaydi, lekin qidirish kerak bo'lgan ma'lumotlar ko'p bo'lsa, sekin bo'lishi mumkin.

Linear search algoritmi bir vaqtning o'zida faqat bitta elementni chiqarib tashlay oladi. Agar birinchi element maqsadli qiymatingizga mos kelsa, qidiruv yakunlanadi. Lekin u oxirida bo'lsa yoki list'da umuman bo'lmasa, linear search algoritmi har bir elementni tekshirib chiqishi kerak. Algoritm har safar elementni maqsadli qiymat bilan solishtirganda search space'ni aynan bittaga kamaytiradi.

Ma'lumotlar sort qilingan bo'lishini talab qiladigan binary search'dan farqli o'laroq, linear search'ni sort qilinmagan ma'lumotlarda ham ishlatish mumkin. U list'ni istalgan tartibda ko'zdan kechirib, har bir qiymatni chapdan o'ngga qarab maqsadli qiymat bilan solishtiradi. Linear search algoritmi kichik list'lar hamda linked list'lar kabi o'rta elementga to'g'ridan-to'g'ri murojaat qilishni qo'llab-quvvatlamaydigan ma'lumotlar tuzilmalari uchun yaxshi tanlov. U faqat bir marta qidirish kerak bo'lganda yoki barcha mos qiymatlarni topish kerak bo'lganda ham yaxshi ishlaydi.

Bunga qarama-qarshi ravishda, binary search har bir taqqoslashda qolgan elementlarning yarmini chiqarib tashlaydi. Elementlarni birma-bir tekshirish o'rniga, u search space'ni qayta-qayta ikkiga bo'ladi. Sort qilingan ma'lumotlar tuzilmalari bilan ishlaganda binary search'dan foydalaning. U katta list'lar, takroriy qidiruvlar va tezlik muhim bo'lgan holatlar uchun juda mos keladi.

Linear va binary search'ning search space'ni qanday kamaytirishi ularning qanchalik tez ishlashiga ta'sir qiladi. Big O notation kiruvchi ma'lumotlar hajmi oshgani sari dasturning ishlash vaqti qanday o'zgarishini tushuntirishga yordam beradi. Big O notation yordamida siz qancha ma'lumotingiz borligiga qarab qidiruvingiz 30 qadam yoki 30 000 qadam olishini oldindan aytib bera olasiz.

Binary va linear search'dan tashqari, ma'lumotlarni topish uchun hash-based search'dan ham foydalanishingiz mumkin. Hash funksiyalar ma'lumotlarni to'g'ridan-to'g'ri hash table'dagi muayyan joylarga map qiladi, bu esa ma'lumotlarning sort qilingan holda qolishi shart bo'lmasa, lookup'larni tezroq qiladi. Hash table lookup'lari o'rtacha O(1) time complexity'ga ega, shuning uchun key orqali to'g'ridan-to'g'ri murojaat qilishda ular binary search'ning O(log n)'idan ham tezroq. Binary search esa sort qilingan ma'lumotlar bilan yaxshiroq ishlaydi va tartibga asoslangan amallarni qo'llab-quvvatlaydi. To'g'ri usul ma'lumotlaringiz qanday tuzilganiga va qidiruvdan nima kutayotganingizga bog'liq.

Python'da binary search'ni amalga oshirish

Endi binary search nima ekanini va u qanday ishlashini bilganingizdan so'ng, Python'da binary search'ni amalga oshirishning bir nechta usulini ko'rib chiqamiz.

Python, har qanday dasturlash tili kabi, binary search algoritmlarini amalga oshirishning moslashuvchan usullarini taqdim etadi. U sizga oddiy, tez yoki built-in yechim kerakmi, ehtiyojlaringizga eng mos keladigan yondashuvni tanlash imkonini beradi. Quyida binary search'ni amalga oshirishning eng keng tarqalgan uchta usuli keltirilgan:

Recursive usulda amalga oshirish
Iterative binary search (while loop yordamida)
Python'ning built-in bisect modulidan foydalanish

Binary search'ni recursive usulda amalga oshirish

Binary search'ning recursive implementation'i masalalarni yechishda divide-and-conquer yondashuviga amal qiladi. U ma'lumotlarni bo'ladi, bir yarmini tekshiradi va so'ngra xuddi shu mantiqni qolgan tegishli yarmiga qo'llaydi. Recursive usul binary search'ni funksiyani takroran chaqirish orqali masalani yechish yo'li bilan qo'llaydi.

Har bir qadamda recursive chaqiruv sort qilingan massiv yoki list'ning kichikroq qismiga e'tibor qaratadi. U maqsadli qiymatni topguncha yoki hech qanday element qolmaguncha search space'ni kamaytirib boradi. Natijada logarithmic time complexity hosil bo'ladi va list hajmi oshgani sari qidiruv oddiy linear search'dan ancha tezroq bo'ladi.

Biroq bu yondashuvning cheklovi bor: har bir recursive chaqiruv call stack'ga yangi qatlam qo'shadi. U qidiruv tugaguncha funksiya chaqiruvlarini faol holda saqlab turadi. Recursive usul iterative yondashuvga qaraganda ko'proq xotira ishlatadi. Biroq binary search'ga bir necha qadamgina kerak bo'ladi, shuning uchun qo'shimcha xotira sarfi amalda kamdan-kam muammo tug'diradi. Ko'plab dasturchilar qo'shimcha xotira sarfidan qochish uchun unumdorlik muhim bo'lgan tizimlarda iterative versiyani tanlaydi.

def binary_search_recursive(arr, target, left=0, right=None):

    if right is None:
        right = len(arr) - 1
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
result = binary_search_recursive(numbers, 8)
print(f"Found at index: {result}")  # Output: Found at index: 3

Recursive binary search algoritmi quyidagicha ishlaydi:

1-qadam: Agar right berilmagan bo'lsa (ya'ni u None bo'lsa), butun search space'ni belgilash uchun uni oxirgi index'ga tenglang.
2-qadam: Agar left right'dan katta bo'lsa, search space bo'sh. Funksiya maqsadli element mavjud emasligini ko'rsatish uchun -1 qaytaradi.
3-qadam: O'rta index'ni floor division operatori (//) yordamida toping: mid = (left + right) // 2. Masalan, (0 + 9) // 2 natijasi 4 ga teng.
4-qadam: O'rta elementni maqsadli qiymat bilan solishtiring. Agar ular mos kelmasa, algoritm qidirishni davom ettiradi. Sizning misolingizda 4-index'dagi qiymat 10, lekin siz 8 ni qidiryapsiz, shuning uchun ular mos kelmaydi. Binary search algoritmi hali index qaytara olmagani uchun qidirishda davom etadi.
5-qadam: Agar o'rta qiymat maqsadli sondan kichik bo'lsa, mid + 1 dan boshlab o'ng yarmida qidiring. Agar katta bo'lsa, mid - 1 da tugaydigan chap yarmida qidiring.
6-qadam: Funksiya muvaffaqiyatli bo'lganda maqsadli elementning index'ini, qidiruv muvaffaqiyatsiz tugaganda esa -1 ni qaytaradi va natijani kutib turgan recursive chaqiruvlarga uzatadi.

Eslatma: // operatori ikki sonni qoldiqni saqlamasdan bo'ladi. Masalan, (0 + 9) // 2 natijasi 4.5 emas, 4 ga teng bo'ladi.

Iterative binary search (while loop yordamida)

Agar sizga tezlik va ishonchlilik kerak bo'lsa, iterative usulni tanlaganingiz ma'qul. Recursion'dan farqli o'laroq, u katta dataset'larni xotira yetishmay qolishidan qo'rqmasdan qayta ishlaydi**.** Binary search'ning iterative versiyasi qidiruv oralig'ini toraytirish uchun recursive funksiya chaqiruvlari o'rniga while loop'dan foydalanadi. U maqsadli elementni topguncha yoki uning mavjud emasligini tasdiqlaguncha bu jarayonni takrorlaydi.

Iterative binary search algoritmi qidiruv oralig'ingiz chegaralarini kuzatib borish uchun ikkita pointer'ga tayanadi. Bu nima sodir bo'layotganini kuzatib borish va har qanday xatoni aniqlashni osonlashtiradi. Algoritm bitta loop ichida ishlagani sababli, ko'plab boshlovchilar iterative binary search'ni o'rganish osonroq deb bilishadi. U funksiya chaqiruvlari stack'i qanday ishlashini o'ylab o'tirmasdan har bir qadamni birma-bir kuzatish imkonini beradi.

Keling, binary search'ni while loop yordamida iterative tarzda amalga oshiramiz. Ushbu sort qilingan list'dan 13 ni qidirasiz:

def binary_search_iterative(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
result = binary_search_iterative(numbers, 13)
print(f"Found at index: {result}")  # Output: Found at index: 6

Iterative binary search algoritmi quyidagicha ishlaydi:

1-qadam: Qidiruv oralig'ini belgilash uchun left pointer'ni 0-index'ga, right pointer'ni esa 9-index'ga o'rnating.
2-qadam: Qidiruv oralig'i bo'sh emasligiga ishonch hosil qilish uchun loop'ni left right pointer'dan kichik yoki unga teng bo'lib turgan vaqtda ishga tushiring.
3-qadam: O'rta index'ni mid = (left + right) // 2 yordamida toping.
4-qadam: Moslikni tekshirish uchun o'rta elementni maqsadli element bilan solishtiring.
5-qadam: Agar o'rta element maqsadli elementdan kichik bo'lsa, o'ng yarmida qidirish uchun left pointer'ni mid + 1 ga o'rnating. Agar katta bo'lsa, chap yarmida qidirish uchun right pointer'ni mid - 1 ga o'rnating.
6-qadam: Agar maqsadli element topilmasa, u sort qilingan list'da yo'qligini ko'rsatish uchun -1 qaytaring.

Python'ning built-in bisect modulidan foydalanish

Python binary search'ni amalga oshirish uchun optimallashtirilgan built-in bisect modulini taqdim etadi. Unda binary search uchun tayyor built-in funksiyalar bor, shuning uchun algoritmlarni o'zingiz yozishingiz shart emas. bisect moduli sort qilingan list'dagi insertion point'larni topishga yordam beradi. Undan har safar element qo'shganingizda butun list'ni qayta sort qilmasdan, sort qilingan ma'lumotlar tuzilmalarini saqlab turish uchun foydalanishingiz mumkin**.**

bisect moduli ichki mantiqi uchun C'dan foydalanadi, bu esa uni oddiy Python implementation'laridan ancha tezroq qiladi. U o'z-o'zidan element mavjud yoki yo'qligini ko'rsatmaydi. Lekin undan elementlarni qidirish va ularni sort qilingan list'ga ishni sekinlashtirmasdan qo'shish uchun foydalanishingiz mumkin.

Keling, bisect modulidan qanday foydalanishni bir nechta amaliy misollar bilan ko'rib chiqamiz.

import bisect

numbers = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

# Find the insertion point for your value
pos = bisect.bisect_left(numbers, 40)
print(f"Position: {pos}")  # Output: Position: 3

# Check if the element exists
target = 40
pos = bisect.bisect_left(numbers, target)
if pos < len(numbers) and numbers[pos] == target:
    print(f"Found {target} at index {pos}")
else:
    print(f"{target} not found")

# Insert while maintaining sorted order
bisect.insort(numbers, 41)
print(numbers)  # Output: [10, 20, 30, 40, 41, 50, 60, 70, 80, 90, 100]

Quyida bisect moduli qanday ishlashi tushuntirilgan:

1-qadam: bisect_left(numbers, 41) list sort qilingan holda qolishi uchun 41 ni qayerga qo'yish kerakligini aytadi.
2-qadam: Pozitsiya list'dan tashqarida emasligini tasdiqlash uchun pos < len(numbers) ekanini tekshiring.
3-qadam: numbers[pos]'ga qarang va u maqsadli soningizga mos kelishini tekshiring.
4-qadam: Agar pozitsiya diapazondan tashqarida bo'lsa yoki qiymat boshqacha bo'lsa, maqsadli soningiz list'da yo'q.
5-qadam: bisect.insort(numbers, 41) elementni bitta qadamda to'g'ri joyga qo'shadi.

Siz Python'da binary search'dan foydalanishning uch xil usulini o'rgandingiz. Uchalasi ham ishlaydi, lekin ular tezlik va xotira sarfi bo'yicha farq qiladi. Space va time complexity'ni tushunish eng yaxshi variantni tanlashga yordam beradi.

Space va time complexity'ni tushunish

Time complexity ma'lumotlar o'sgani sari algoritm ishlashi uchun qancha vaqt ketishini o'lchaydi. U algoritm turli vaziyatlarda qanchalik yaxshi ishlashi haqida umumiy tasavvur beradi. Masalan, binary search algoritmi O(log n) logarithmic time complexity'ga ega. Bu algoritm qidiruv oralig'ini doimiy ravishda ikkiga bo'lib boradi va shuning uchun natijalarni tezroq topadi degani. O(log n) o'rniga constant-time lookup'lar kerak bo'lgan joylarda hashmap lookup yaxshiroq tanlov hisoblanadi.

Ma'lumotlar hajmini ikki baravar oshirsangiz, umumiy qidiruv vaqtiga atigi bitta qadam qo'shiladi. Masalan, agar 1 000 ta element orasidan qidirayotgan bo'lsangiz, O(log n) bilan bu taxminan 10 qadamni oladi. Bu 10 qadamni 1 000 ni 1 ga yetguncha qayta-qayta 2 ga bo'lish orqali ko'rishingiz mumkin: 1 000, 500, 250, 125, 62, 31, 15, 7, 3 va nihoyat 1.

Har bir qadam ma'lumotlarni ikkiga bo'lgani uchun list'ingizni 2 000 ta elementgacha ikki baravar oshirish atigi bitta qo'shimcha qadam qo'shadi va jami 11 qadam bo'ladi. Binary search oldindan aytib bo'ladigan va sekin o'sadigan tabiati tufayli katta dataset'lar uchun yaxshi ishlaydi.

Space va time complexity tasviri

Boshqa tomondan, linear search O(n) linear time complexity'ga ega. Bu algoritm elementlarni birma-bir tekshiradi, shuning uchun qidiruv vaqti list hajmi bilan bir xil sur'atda o'sadi degani. Agar linear search yordamida 1 000 ta element orasidan qidirsangiz, qadamlar sonini 10 ga kamaytirish uchun ikkiga bo'lish jarayonidan foydalana olmaysiz. Algoritm har bir elementni boshidan boshlab tekshiradi va 1 000 tagacha qadam talab qilishi mumkin. Shu sababli linear search kichik dataset'lar va oddiy vazifalar uchun eng yaxshi ishlaydi.

Python'dagi binary search'ning uchala implementation'i ham O(log n) time complexity'ga ega. bisect moduli real foydalanishda odatda tezroq ishlaydi, lekin uning time complexity'si o'zgarmaydi. Implementation'ni space complexity va kodning o'qilishi osonligi kabi boshqa omillarga qarab tanlang.

Space complexity — algoritm ishlashi uchun talab qilinadigan xotira miqdori. Iterative binary search list o'sgani sari qo'shimcha xotiraga muhtoj bo'lmaydi. U O(1) constant space complexity'ga ega. Bu dataset qanchalik katta bo'lishidan qat'i nazar, algoritm egallaydigan joy miqdori o'zgarmasligini anglatadi.

Kiruvchi ma'lumotlar hajmidan qat'i nazar, ma'lumotlarni qidirish uchun unga faqat uchta o'zgaruvchi (left, right, mid) kerak. 30 ta elementni qidirasizmi yoki 30 000 tasini, xotira sarfi bir xil qoladi. Bu uni katta dataset'lar uchun yaxshiroq variantga aylantiradi, chunki u haddan tashqari ichma-ich chaqiruvlar keltirib chiqaradigan muammolardan xoli.

Bunga qarama-qarshi ravishda, binary search'ning recursive versiyasi qidiruv chuqurlashgani sari ko'proq xotira ishlatadi. Call stack tufayli u O(log n) space complexity'ga ega. Recursion ishlatilganda har bir qadam yangi ichma-ich chaqiruv yaratadi, kompyuter esa joriy chaqiruv tugagandan keyin qayerga qaytish kerakligini bilish uchun ularni kuzatib boradi.

Funksiya o'zini o'zi har safar chaqirganda ko'proq xotira ishlatadi. Recursion qanchalik chuqurlashsa, shunchalik ko'p xotira sarflanadi. Bu ortib boruvchi xotira sarfi dataset katta bo'lganda dasturning ishdan chiqishiga olib kelishi mumkin.

Binary search'ning amaliy qo'llanilishi

Binary search — sort qilingan ma'lumotlar bilan ishlashning samarali usuli. Quyida undan foydalanish mumkin bo'lgan ba'zi keng tarqalgan vaziyatlar keltirilgan:

Sort qilingan list'lar yoki massivlarda qidirish

Binary search'ning asosiy qo'llanilishi — massiv yoki list kabi sort qilingan to'plamdan elementlarni topish. Masalan, streaming ilovasida filmlar odatda alifbo tartibida joylashtiriladi. Bu sizga butun ro'yxatni aylantirib chiqmasdan kerakli filmni topishga yordam beradi. Binary search ma'lumotlaringiz bilan aynan shu ishni qiladi. Minglab nomlarni birma-bir ko'rib chiqish o'rniga, qidirayotgan muayyan qiymatingizni bor-yo'g'i bir necha tekshiruvda topishingiz mumkin.

import bisect

# Streaming service movie library (sorted)
available_movies = ["Abbott elementary", "Blackish", "Fast and furious", "Game of thrones", "Insecure", "Jumanji","Lord of the rings", "Moana", "Shrinking", "Toy Story"]

# Check if a movie is available
movie_to_watch = "Moana"
position = bisect.bisect_left(available_movies, movie_to_watch)

if position < len(available_movies) and available_movies[position] == movie_to_watch:
    print(f"'{movie_to_watch}' is available to stream")
else:
    print(f"'{movie_to_watch}' is not in the catalog")

Tartiblangan ma'lumotlarda qo'shish pozitsiyalarini topish

Agar allaqachon sort qilingan list'ga yangi element qo'shsangiz, binary search unga to'g'ri pozitsiyani topishga yordam beradi. Bu tizimlarni tartibli saqlaydi, shuning uchun hamma narsani qaytadan sort qilishingiz shart bo'lmaydi. Masalan, telefoningizdagi kalendar ilovasiga yangi uchrashuv qo'shganingizda, tadbirlar allaqachon vaqt bo'yicha sort qilingan bo'ladi. Binary search yangi tadbir qayerga tegishli ekanini O(log n) vaqtda topishga yordam beradi, shunda uni butun jadvalingizni qayta sort qilmasdan qo'shishingiz mumkin.

import bisect
from datetime import datetime

# Events sorted by start time
event_times = [
    datetime(2026, 2, 5, 9, 0),   # 9:00 AM
    datetime(2026, 2, 5, 10, 30), # 10:30 AM
    datetime(2026, 2, 5, 14, 0),  # 2:00 PM
    datetime(2026, 2, 5, 16, 30)  # 4:30 PM
]

# Add a new meeting at 12:00 PM
new_meeting = datetime(2026, 2, 5, 12, 0)
position = bisect.bisect_left(event_times, new_meeting)
event_times.insert(position, new_meeting)

print(f"Meeting inserted at position {position}")
print(f"Total events: {len(event_times)}")

Log'lar, ID'lar yoki timestamp'lar bo'yicha qidirish

Log fayllar, transaction'lar va time series ma'lumotlari ko'pincha timestamp yoki ID bo'yicha sort qilingan bo'ladi. Binary search'dan foydalanish muayyan qiymatlar yoki vaqt oraliqlarini qidirishni tezlashtiradi. Bu yondashuv data science sohasida qimmatli**,** u yerda analyst'lar katta time series dataset'lari bilan ishlaydi.

import bisect

# User IDs from sorted database query
user_ids = [1001, 1045, 1089, 1123, 1167, 1201, 1245, 1289, 1334, 1378]

# Find user with ID 1200
target_id = 1200
pos = bisect.bisect_left(user_ids, target_id)

if pos < len(user_ids) and user_ids[pos] == target_id:
    print(f"User {target_id} found at index {pos}")
else:
    if pos < len(user_ids):
        print(f"User {target_id} not found. Next highest ID is {user_ids[pos]} at index {pos}.")
    else:
        print(f"User {target_id} not found. This ID is higher than every ID in the database.")

Ma'lumotlar bazalari, indexing va intervyu masalalarida foydalanish

Ma'lumotlar bazalari indexing uchun binary search'ga o'xshash texnikalardan, masalan, B-tree va B+ tree'lardan foydalanadi. Bu usullar har bir satrni tekshirib chiqmasdan query'ingizga mos qiymatni topishga yordam beradi. Binary search katta dataset'lar keng tarqalgan data science sohasida ham foydali. NumPy va pandas kabi data science kutubxonalari sort qilingan massivlar yoki index'lar bilan ishlaganda ichki tarzda binary search'dan foydalanadi.

Binary search texnik intervyularda ham ko'p uchraydigan mavzu. U muammolarni yechish uchun algoritmlarni qanchalik yaxshi tushunishingiz va qo'llay olishingizni sinaydi. Masalan, intervyu oluvchilar sizdan katta integer'ning kvadrat ildizini topishni yoki siljitilgan list'dagi eng kichik elementni aniqlashni so'rashi mumkin. Binary search pattern'larini tushunib olganingizdan so'ng, bunday masalalarni taniy va yecha olasiz.

Keng tarqalgan xatolar va best practice'lar

Binary search samarali, lekin noto'g'ri implementation xatolarga olib kelishi mumkin. Quyida ba'zi keng tarqalgan xatolar va best practice'lar keltirilgan.

Sort qilinmagan ma'lumotlar tuzilmalarida binary search'dan foydalanish

Binary search yaxshi ishlashi uchun sort qilingan ma'lumotlarni talab qiladi. Agar uni sort qilinmagan ma'lumotlarda ishga tushirishga harakat qilsangiz, noto'g'ri javob olasiz yoki list'da haqiqatda mavjud bo'lgan qiymatlarni o'tkazib yuborasiz. Algoritm list'ingizning chap yoki o'ng yarmida qidirishni hal qilishdan oldin avval maqsadli qiymatni o'rta qiymat bilan solishtiradi. Agar ma'lumotlaringiz sort qilinmagan bo'lsa, bu qaror noto'g'ri bo'lib chiqadi.

# Error: wrong answer
unsorted_list = [20, 30, 25, 10, 5, 15]
result = binary_search_iterative(unsorted_list, 5)

# Best practice: correct answer

# Method 1: Using sorted()
unsorted_list = [20, 30, 25, 10, 5, 15]
sorted_list = sorted(unsorted_list)
result = binary_search_iterative(sorted_list, 5)
print(unsorted_list)  # Still [20, 30, 25, 10, 5, 15]
print(sorted_list)    # Now [5, 10, 15, 20, 25, 30]

# Method 2: Using .sort() 
unsorted_list = [20, 30, 25, 10, 5, 15]
unsorted_list.sort()
result = binary_search_iterative(unsorted_list, 5)
print(unsorted_list)  # Now [5, 10, 15, 20, 25, 30]

Binary search'dan foydalanishdan oldin har doim ma'lumotlaringizni sort qiling. Agar ma'lumotlarni tashqi manbadan olsangiz, ular allaqachon sort qilingan deb taxmin qilmang. Avval ularni yangi sort qilingan list yaratadigan sorted() yoki asl list'ning o'zini sort qiladigan .sort() yordamida sort qiling yoki tartibni o'zingiz tekshiring. Agar bir xil ma'lumotlarda tez-tez qidirsangiz, har bir qidiruvdan oldin sort qilish o'rniga ularni yuklayotganda bir marta sort qiling. Agar sort qilish ko'p vaqt olsa va sizga faqat bir-ikki marta qidirish kerak bo'lsa, linear search'dan foydalaning.

Takroriy qiymatlarni hisobga olmaslik

Sort qilingan list'da turli qiymatlar bo'lishi mumkin va ulardan ba'zilari bir necha marta uchrashi mumkin. Bunday holatda standart binary search o'zi topgan birinchi moslikda to'xtaydi, bu esa qiymatning birinchi yoki oxirgi nusxasi bo'lmasligi mumkin. Shuning uchun, agar qidiruv mezoningiz muayyan index'ni topishni talab qilsa, algoritm qiymatning qaysi nusxasini qaytarishiga ishonch hosil qila olmaysiz.

# ERROR: binary search on a list with duplicate values
def standard_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid        # Returns any occurrence - unpredictable!
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

arr = [1, 2, 2, 2, 2, 3, 4]
result = standard_search(arr, 2)
print(f"Found at index: {result}")  # Might return 1, 2, 3, or 4 - unpredictable!

# BEST PRACTICE: Using bisect
import bisect

# Find first occurrence using bisect_left
first = bisect.bisect_left(arr, 2)
print(f"First occurrence of 2: index {first}")  # Always returns index 1

# Find last occurrence using bisect_right
last = bisect.bisect_right(arr, 2) - 1
print(f"Last occurrence of 2: index {last}")    # Always returns index 4

# Write your own first occurrence search
def find_first(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Keep searching left half for earlier occurrence
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

# Write your own last occurrence search
def find_last(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            left = mid + 1  # Keep searching right half for later occurrence
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

print(f"First occurrence: {find_first(arr, 2)}")  # Always returns 1
print(f"Last occurrence: {find_last(arr, 2)}")    # Always returns 4

Agar sizga birinchi nusxa kerak bo'lsa, moslik topilgandan keyin ham chap yarmida qidirishni davom ettiring. Agar oxirgi nusxa kerak bo'lsa, o'ng yarmida qidirishni davom ettiring. Python'da bunday maxsus qidiruv mezonlarini built-in vositalar yordamida hal qilishingiz mumkin. Birinchi nusxani topish uchun bisect_left()'dan, oxirgisini topish uchun esa bisect_right()'dan foydalaning.

Off-by-one xatolar va cheksiz loop'lar

Qidiruv chegaralari noto'g'ri belgilansa, elementlar o'tkazib yuborilishi yoki cheksiz loop'lar yuzaga kelishi mumkin. Algoritm o'rta elementni qidiruv oralig'idan chiqarib tashlay olmaydi va natijada bir xil qiymat qayta-qayta tekshiriladi**.** Keng tarqalgan xatolarga quyidagilar kiradi:

Chegaralarni mid + 1 yoki mid - 1 o'rniga mid bilan yangilash
Loop shartini <= o'rniga < bilan yozish
Har bir taqqoslashdan keyin chegaralarni o'rta nuqtadan o'tkazib siljitishni unutish

# Code with errors
def buggy_binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:  # error 1: Should be left <= right
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid  # error 2: Should be mid + 1
        else:
            right = mid  # error 3: Should be mid - 1
    return -1

Har bir taqqoslashdan keyin left yoki right chegarasini o'rta nuqtadan o'tkazib siljitish orqali qidiruv oralig'ini kichraytiring. O'rta elementni allaqachon tekshirganingiz uchun uni qayta kiritishingiz shart emas. Agar o'rta qiymat juda kichik bo'lsa, left = mid + 1 qilib o'ng yarmida qidiring. Agar o'rta qiymat juda katta bo'lsa, right = mid - 1 qilib chap yarmida qidiring.

Xulosa

Binary search — sort qilingan massiv yoki list'dan elementlarni topish uchun kuchli va samarali algoritm. U har bir qadamda qidiruv oralig'ini ikkiga bo'lish orqali ishlaydi, bu esa ma'lumotlar kattalashgani sari qidiruvni tezlashtiradi. Bu yondashuv katta dataset'larda unumdorlikni oshiradi va qidiruv amallarini optimallashtiradi.

Binary search'ni o'rganish har qanday tajriba darajasidagi Python dasturchilari uchun muhim. U yaxshiroq algoritmlar yozishga va texnik intervyulardan muvaffaqiyatli o'tishga yordam beradi. O'rganish dastlab qiyin tuyulishi mumkin, lekin mashq qilishda davom etsangiz, osonlashib boradi. Asoslardan boshlang va vaqt o'tishi bilan loop'lar, recursion yoki bisect modulidan qachon foydalanishni o'rganib olasiz.

Bilimingizni sinab ko'rishga tayyormisiz? Python binary search bo'yicha interaktiv quiz'imiz bilan o'zingizni sinang. O'rganganlaringizni eslab qolishingizga yordam beradigan tezkor fikr-mulohaza va har bir savol bo'yicha shaxsiylashtirilgan tushuntirishlarga ega bo'ling.