sort.Search în Go

import "sort"

func Search(n int, f func(int) bool) int
func SearchInts(a []int, x int) int

Ce face sort.Search

sort.Search(n, f) face o căutare binară: presupune că f(i) este false pentru primii indici și true pentru restul, și returnează primul indice unde f devine true. Dacă f nu este niciodată adevărată, returnează n. Face doar aproximativ log₂(n) apeluri.

sort.SearchInts(a, x) caută x într-un slice sortat crescător și returnează poziția unde se află sau unde ar trebui inserat. Nu spune direct dacă l-a găsit: verifici tu i < len(a) && a[i] == x.

Varianta modernă este slices.BinarySearch(a, x), care returnează și un bool ce spune dacă elementul există.

Parametri

Parametru	Descriere
n	Numărul de indici în care se caută (de obicei len(slice)).
f	Condiția verificată pentru un indice; trebuie să fie false, apoi true.
a, x	Pentru SearchInts: slice-ul sortat și valoarea căutată.

Ce returnează

Un indice între 0 și n (sau len(a)).

Exemple

Exemplul 1: Unde se află sau unde s-ar insera o valoare

package main

import (
    "fmt"
    "sort"
)

func main() {
    a := []int{3, 8, 15, 21, 40}
    for _, x := range []int{15, 16, 50} {
        i := sort.SearchInts(a, x)
        gasit := i < len(a) && a[i] == x
        fmt.Printf("%d: indice %d, găsit: %v\n", x, i, gasit)
    }
}

Rezultat

15: indice 2, găsit: true
16: indice 3, găsit: false
50: indice 5, găsit: false

Exemplul 2: Primul produs mai scump de 20 de lei

Prețurile sunt sortate, deci condiția preturi[i] > 20 este falsă la început și adevărată după un punct.

package main

import (
    "fmt"
    "sort"
)

func main() {
    preturi := []float64{4.5, 9.99, 15, 22.5, 31, 48}
    i := sort.Search(len(preturi), func(i int) bool { return preturi[i] > 20 })
    fmt.Println("Primul preț peste 20 de lei:", preturi[i], "la indicele", i)
    fmt.Println("Produse până în 20 de lei:", preturi[:i])
}

Rezultat

Primul preț peste 20 de lei: 22.5 la indicele 3
Produse până în 20 de lei: [4.5 9.99 15]

Exemplul 3: Varianta modernă: slices.BinarySearch

package main

import (
    "fmt"
    "slices"
)

func main() {
    a := []int{3, 8, 15, 21, 40}
    i, gasit := slices.BinarySearch(a, 16)
    fmt.Println(i, gasit)
}

Rezultat

3 false

Greșeli frecvente

• Cauți într-un slice nesortat: căutarea binară dă rezultate greșite fără nicio eroare.
• Consideri că rezultatul lui SearchInts înseamnă „găsit”: verifică mereu și a[i] == x, iar înainte i < len(a).

Comenzi înrudite

• slices.BinarySearch: Caută rapid o valoare într-un slice sortat; returnează poziția (sau unde s-ar insera) și dacă a găsit-o.
• sort.Ints: Sortează crescător, pe loc, un []int, []string sau []float64; IntsAreSorted verifică dacă un []int este deja sortat.