Binary search

Binary search algoritmi qidiruv algoritmlaridan biridir va ma'lumotlarni qidirishda juda samarali hisoblanadi.

Binary search algoritmi qidiruv algoritmlaridan biridir va ma'lumotlarni qidirishda juda samarali hisoblanadi. Bu algoritm faqat tartiblangan (saralangan) ro'yxatlarda ishlaydi. Binary search algoritmining asosiy g'oyasi shundaki, qidirilayotgan elementni ro'yxatning o'rtasidagi element bilan taqqoslash orqali qidiruv hududini har bir bosqichda ikkiga qisqartirishdir.

Binary Search Algoritmining Ishlash Printsipi

1. Boshlang'ich holat:

   • Ro'yxatning boshlanishi va oxirini ko'rsatuvchi left va right indekslari olinadi. left boshlang'ichda 0 ga teng bo'ladi, right esa ro'yxatning oxirgi indeksiga teng bo'ladi.

2. O'rta qiymatni aniqlash:

   • Ro'yxatning o'rtasidagi element indeksini middle = (left + right) // 2 orqali aniqlaymiz.

3. Elementni taqqoslash:

   • Agar o'rta qiymat qidirilayotgan elementga teng bo'lsa, qidiruv muvaffaqiyatli yakunlanadi va bu qiymatning indeksi qaytariladi.
   • Agar qidirilayotgan element o'rta qiymatdan kichik bo'lsa, qidiruvni chap qismda davom ettiramiz (right = middle - 1).
   • Agar qidirilayotgan element o'rta qiymatdan katta bo'lsa, qidiruvni o'ng qismda davom ettiramiz (left = middle + 1).

4. Qidiruvni davom ettirish:

   • Bu jarayon left <= right bo'lguncha takrorlanadi.

5. Element topilmasa:

   • Agar qidiruv oxiriga yetib, element topilmasa, qidiruv muvaffaqiyatsiz yakunlanadi va -1 yoki boshqa mos qiymat qaytariladi.

Python Dastur Kodi

Quyida binary search algoritmi Python dasturlash tilida qanday yozilishi ko'rsatilgan:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
 
    while left <= right:
        middle = (left + right) // 2
 
        # O'rta elementni tekshirish
        if arr[middle] == target:
            return middle
 
        # Agar target o'rta elementdan kichik bo'lsa
        elif arr[middle] > target:
            right = middle - 1
 
        # Agar target o'rta elementdan katta bo'lsa
        else:
            left = middle + 1
 
    # Element topilmadi
    return -1
 
# Misol uchun:
arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
 
result = binary_search(arr, target)
if result != -1:
    print(f"Element {target} index {result} da topildi.")
else:
    print("Element topilmadi.")

Kodingiz qanday ishlashini tushuntirish:

• arr: Qidirilayotgan saralangan ro'yxat.
• target: Qidirilayotgan element.
• left va right: Ro'yxatning qidiruv boshlang'ich va oxirgi indekslari.
• middle: Qidiruv uchun o'rta elementning indeksi.
• while tsikli: Qidiruv jarayonini boshqaradi va qidiruv tugaguncha davom etadi.
• Natija: Agar qidirilayotgan element ro'yxatda bo'lsa, uning indeksi qaytariladi, aks holda -1 qiymati qaytariladi.

Binary search algoritmining vaqt murakkabligi O(log n), ya'ni ro'yxatning kattaligi oshgan sari, qidiruv vaqtining o'sishi juda sekinlashadi. Shu sababli, bu algoritm katta ro'yxatlarda qidiruv amalga oshirishda juda samarali hisoblanadi.

Misol: Binary Search funksiyasi

def binary_search(arr, target):
    left, right = 0, len(arr) - 1  # Boshlang'ich va oxirgi indekslarni belgilash
 
    while left <= right:  # Qidiruv davom etadi, to chap indeks o'ng indeksdan kichik yoki teng bo'lsa
        mid = (left + right) // 2  # O'rta indeksni hisoblash
 
        if arr[mid] == target:  # Agar o'rta element qidirilayotgan qiymatga teng bo'lsa
            return mid  # Qidiruv tugadi, indeksni qaytaradi
        elif arr[mid] < target:  # Agar qidirilayotgan qiymat o'rta elementdan katta bo'lsa
            left = mid + 1  # Qidiruvni o'ng yarimga o'tkazamiz
        else:  # Agar qidirilayotgan qiymat o'rta elementdan kichik bo'lsa
            right = mid - 1  # Qidiruvni chap yarimga o'tkazamiz
 
    return -1  # Agar qidirilayotgan qiymat topilmasa, -1 qaytariladi
 
# Misol ro'yxat va qidiriladigan qiymat
numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7
 
# Binary search funksiyasini chaqirish
result = binary_search(numbers, target)
 
if result != -1:
    print(f"Qiymat {target} indeksi {result} da topildi.")
else:
    print(f"Qiymat {target} topilmadi.")

Izohlar:

• Tartiblangan ro'yxat: numbers — bu tartiblangan ro'yxat, va target — qidirilayotgan qiymat.
• O'rta indeks: O'rta indeks (left + right) // 2 formulasi orqali aniqlanadi.
• Qidiruv jarayoni: Agar o'rta element qidirilayotgan qiymatga teng bo'lmasa, qidiruvni faqat bir yarimda davom ettiramiz, bu algoritmni juda samarali qiladi.
• Loop orqali qidiruv: Qidiruv while siklida takrorlanadi va natijada qiymat topilsa, uning indeksi, topilmasa, -1 qaytariladi.

Natija:

Agar target = 7 bo'lsa, bu qiymat 3-indeksda joylashgan va Qiymat 7 indeksi 3 da topildi. deb chop etiladi.