Binary Search

Ikkilik qidiruv (Binary Search) — bu saralangan (tartiblangan) massivdan qidirilayotgan elementning o'rnini topish uchun qo'llaniladigan juda tezkor qidiruv algoritmidir.

Ushbu yondashuvda qidiruv maydoni har bir qadamda ikkiga bo'linadi va element doimo massivning o'rtasidagi element bilan taqqoslanadi.

[!IMPORTANT] Ikkilik qidiruv faqat va faqat elementlari oldindan saralangan massivlarda ishlaydi. Agar elementlar tartiblanmagan bo'lsa, ularni avval saralab olish lozim.

Ikkilik qidiruv qanday ishlaydi?

Ikkilik qidiruv algoritmini ikki xil usulda amalga oshirish mumkin:

1. Iterativ usul (sikl yordamida)
2. Rekursiv usul ("Bo'lib ol va hukmronlik qil" usulida)

Har ikkala usulning umumiy mantiqiy bosqichlari quyidagicha:

1-qadam: Boshlang'ich massiv

Qidiruv bajariladigan massiv quyidagicha berilgan:

Dastlabki saralangan massiv (Initial array)

Aytaylik, biz x = 4 elementini qidirmoqdamiz.

2-qadam: Ko'rsatkichlarni o'rnatish

Massivning eng boshiga low va eng oxiriga high ko'rsatkichlarini o'rnatamiz:

low va high ko'rsatkichlarini o'rnatish

3-qadam: O'rtadagi elementni topish

Massivning o'rtasidagi indeksni hisoblaymiz: mid = (low + high) / 2 Hozirgi holatda mid = (0 + 9) / 2 = 4 bo'lib, arr[mid] = 6 ga teng.

O'rta elementni aniqlash (Mid element)

4-qadam: Qidirilayotgan elementni o'rta element bilan taqqoslash

• Agar x == arr[mid] bo'lsa, element topildi va mid indeksi qaytariladi.
• Agar x < arr[mid] bo'lsa (bizning misolda 4 < 6), demak izlanayotgan son o'rta elementdan chapda joylashgan. Shuning uchun high = mid - 1 qilib, o'ng qismni qidiruvdan butunlay chiqarib tashlaymiz:

O'ng qism bekor qilinib, qidiruv chap tomonda davom ettiriladi

5-qadam: Yangi oraliqda o'rtani qayta hisoblash

Endi low = 0 va high = 3. Yangi o'rta indeks: mid = (0 + 3) / 2 = 1 bo'ladi, arr[mid] = 3.

Yangi oraliqdagi o'rta element (mid = 1, arr[mid] = 3)

Endi x ni yana taqqoslaymiz: 4 > 3, demak element mid dan o'ng tomonda. Shuning uchun low = mid + 1 qilib, chap qismni chiqarib tashlaymiz:

6-qadam: Element topildi

Endi low = 2, high = 3. mid = (2 + 3) / 2 = 2 bo'lib, arr[mid] = 4 ga teng bo'ladi. x == arr[mid] sharti bajarildi — element topildi!

Qidirilgan element topildi (indeksi: 2)

Agar low > high holati yuzaga kelsa va element topilmasa, demak bu son massivda mavjud emas.

Ikkilik qidiruv soxta kodi

Iterativ usul:

do until low > high
    mid = (low + high) / 2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid])
        low = mid + 1
    else
        high = mid - 1
return -1

Rekursiv usul:

binarySearch(arr, x, low, high)
    if low > high
        return -1
    else
        mid = (low + high) / 2
        if x == arr[mid]
            return mid
        else if x > arr[mid]
            return binarySearch(arr, x, mid + 1, high)
        else
            return binarySearch(arr, x, low, mid - 1)

Dasturiy namunalar

Quyida iterativ va rekursiv usullarning to'liq dasturiy kodi keltirilgan:

// Go tilida Binary Search (Iterativ va Rekursiv)
package main

import "fmt"

// Iterativ ikkilik qidiruv
func binarySearchIterative(arr []int, x int) int {
	low := 0
	high := len(arr) - 1

	for low <= high {
		mid := low + (high-low)/2

		if arr[mid] == x {
			return mid
		}

		if arr[mid] < x {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}

	return -1
}

// Rekursiv ikkilik qidiruv
func binarySearchRecursive(arr []int, x, low, high int) int {
	if low > high {
		return -1
	}

	mid := low + (high-low)/2

	if arr[mid] == x {
		return mid
	}

	if arr[mid] > x {
		return binarySearchRecursive(arr, x, low, mid-1)
	}

	return binarySearchRecursive(arr, x, mid+1, high)
}

func main() {
	arr := []int{3, 4, 5, 6, 7, 8, 9}
	x := 4

	result := binarySearchIterative(arr, x)
	if result == -1 {
		fmt.Println("Element topilmadi")
	} else {
		fmt.Printf("Element %d-indeksda topildi (Iterativ)\n", result)
	}

	resultRec := binarySearchRecursive(arr, x, 0, len(arr)-1)
	fmt.Printf("Element %d-indeksda topildi (Rekursiv)\n", resultRec)
}

Ikkilik qidiruvning murakkabligi

Vaqt murakkabligi

• Eng yaxshi holat (Best Case): O(1) — agar qidirilayotgan element massivning qoq o'rtasida turgan bo'lsa.
• Eng yomon holat (Worst Case): O(log n) — massiv har qadamda teng ikkiga qisqarib boradi (N/2, N/4, ..., 1).
• O'rtacha holat (Average Case): O(log n).

Masalan, 1 000 000 ta saralangan elementdan iborat massivda istalgan elementni topish uchun ko'pi bilan atigi 20 ta taqqoslash yetarli bo'ladi!

Xotira murakkabligi

• Iterativ usulda: O(1) (qo'shimcha xotira sarflanmaydi).
• Rekursiv usulda: O(log n) (chaqiruvlar steki uchun).

Ikkilik qidiruvning qo'llanilishi

• Ma'lumotlar bazalarida (B-Tree va B+ Tree indekslarida tezkor qidiruv).
• Dasturlash tillarining standart kutubxonalarida (masalan, C++ da std::binary_search, lower_bound, upper_bound, Go da sort.Search).
• Javob bo'yicha ikkilik qidiruv (Binary search on answer) — optimallashtirish masalalarini hal qilishda.