Qidiruv

Qidiruv - to’plamdan kerakli elementni topish. Ikki asosiy usul bor va tanlov ma’lumot tartiblanganmi yo’qmi - shunga bog’liq.

Linear search - boshdan oxirigacha har elementni tekshiradi. Tartib talab qilmaydi, lekin O(n). Binary search - faqat tartiblangan ma’lumotda ishlaydi: o’rtaga qaraydi, izlanayotgan qiymat undan kichik yoki katta ekaniga qarab yarmini tashlaydi, va shunday takrorlaydi. Har qadamda hajm ikkiga bo’lingani uchun O(log n).

Taqqoslash

Usul	Talab	Murakkablik
Linear search	yo’q	`O(n)`
Binary search	tartiblangan bo’lishi	`O(log n)`

Farqni his qiling: million elementda linear ~million qadam, binary esa ~20 qadam.

search.go


package main
 
import (
    "fmt"
    "slices"
)
 
// O(n): tartibsiz slice da ham ishlaydi
func linearSearch(a []int, target int) int {
    for i, v := range a {
        if v == target {
            return i
        }
    }
    return -1
}
 
// O(log n): faqat tartiblangan slice da
func binarySearch(a []int, target int) int {
    lo, hi := 0, len(a)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2 // overflow-dan xavfsiz
        switch {
        case a[mid] == target:
            return mid
        case a[mid] < target:
            lo = mid + 1
        default:
            hi = mid - 1
        }
    }
    return -1
}
 
func main() {
    a := []int{1, 3, 4, 7, 9, 11, 15} // tartiblangan
    fmt.Println("linear 9:", linearSearch(a, 9))
    fmt.Println("binary 9:", binarySearch(a, 9))
 
    // amalda: standart kutubxona
    idx, found := slices.BinarySearch(a, 11)
    fmt.Println("slices.BinarySearch 11:", idx, found)
}


$ go run search.go
linear 9: 4
binary 9: 4
slices.BinarySearch 11: 5 true

slices.BinarySearch indeks bilan birga found (topildimi) qaytaradi. Element yo’q bo’lsa ham, uni tartibni buzmasdan qayer joylash kerakligini (indeks) beradi - insert uchun qulay.

Xulosa: Tartiblangan ma’lumotda har doim binary search. Amalda slices.BinarySearch ni ishlating.

Manba / batafsil: slices.BinarySearch - pkg.go.dev