Qalin lug'atdan bitta so'zni qidirayotganingizni tasavvur qiling. Birinchi sahifadan boshlab, bittalab varaqlab chiqmaysiz — o'rtasidan ochasiz, kerakli so'z u yerdagi so'zdan oldinmi keyinmi ekanini ko'rasiz, va faqat mos yarmini davom ettirasiz. Har safar qidiruv maydoningiz yarmiga qisqaradi.

Bu — Binary Search (ikkilik qidiruv), va u "Binary Tree Basics" darsida ko'rgan BST qidiruvining, endi tartiblangan slice ustida qo'llanilgan ko'rinishi. Muhim shart: bu algoritm faqat allaqachon saralangan ma'lumotda ishlaydi — aks holda "o'rtadagi qiymatdan kichikmi kattami" degan taqqoslash ma'nosiz bo'lib qoladi.

package main

import "fmt"

func binarySearch(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := (low + high) / 2
		if nums[mid] == target {
			return mid
		}
		if nums[mid] < target {
			low = mid + 1 // target o'ngroqda — chap yarmini tashlaymiz
		} else {
			high = mid - 1 // target chaproqda — o'ng yarmini tashlaymiz
		}
	}
	return -1 // topilmadi
}

func main() {
	nums := []int{1, 3, 5, 7, 9, 11}
	fmt.Println(binarySearch(nums, 7))
	fmt.Println(binarySearch(nums, 4))
}

low va high — hozircha qidirilayotgan "oynaning" chegaralari. Har bir qadamda mid (o'rta indeks) tekshiriladi: agar aynan shu qiymat bo'lsa, topildi. Aks holda, target middan kattami-kichikmi ekanini bilib, oynaning yarmini butunlay tashlab yuboramiz (lowni yoki highni siljitib). Sikl low > high bo'lganda ("qidiradigan joy qolmadi") to'xtaydi, va bu holatda -1 — "topilmadi" degani.

Bu "har safar yarmini tashlash" strategiyasi juda kuchli: hatto 1 million elementli ro'yxatda ham, binary search ko'pi bilan ~20 marta solishtirish bilan kerakli elementni topadi (chunki 2^20 ≈ 1 million) — buni "Big O Notation" darsida aniqroq ko'ramiz.