`slices.BinarySearch` în Go

Caută rapid o valoare într-un slice sortat; returnează poziția (sau unde s-ar insera) și dacă a găsit-o.

Sintaxă

import "slices"

func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool)
func BinarySearchFunc[S ~[]E, E, T any](x S, target T, cmp func(E, T) int) (int, bool)

Ce face `slices.BinarySearch`

slices.BinarySearch(x, target) caută target într-un slice sortat crescător, prin înjumătățiri succesive. Returnează două valori: indicele unde se află valoarea (sau unde ar trebui inserată ca slice-ul să rămână sortat) și un bool care spune dacă a găsit-o.

slices.BinarySearchFunc(x, target, cmp) caută într-un slice de structuri sortat după un câmp. Funcția cmp(element, target) compară un element cu valoarea căutată, care poate avea alt tip (de exemplu cauți după nume într-un slice de persoane).

Pe un milion de elemente, căutarea binară face cel mult aproximativ 20 de comparații, față de un milion la slices.Index. Înlocuiește sort.SearchInts și sort.Search.

Parametri

Parametru	Descriere
`x`	Slice-ul sortat.
`target`	Valoarea căutată.
`cmp`	Pentru `BinarySearchFunc`: compară un element cu `target`.

Ce returnează

Indicele și true dacă valoarea există; altfel poziția de inserare și false.

Exemple

Exemplul 1: Găsire și inserare păstrând ordinea

package main

import (
    "fmt"
    "slices"
)

func main() {
    note := []int{5, 7, 8, 10}
    i, gasit := slices.BinarySearch(note, 8)
    fmt.Println(i, gasit)

    i, gasit = slices.BinarySearch(note, 9)
    fmt.Println(i, gasit)
    note = slices.Insert(note, i, 9)
    fmt.Println(note)
}

Rezultat

2 true
3 false
[5 7 8 9 10]

Exemplul 2: Căutare după un câmp cu BinarySearchFunc

Slice-ul este sortat după cod poștal. Valoarea căutată este doar codul (string), nu o structură întreagă.

package main

import (
    "cmp"
    "fmt"
    "slices"
)

type Localitate struct {
    Cod, Nume string
}

func main() {
    loc := []Localitate{{"010011", "București"}, {"400001", "Cluj-Napoca"}, {"700001", "Iași"}, {"900001", "Constanța"}}
    cauta := func(cod string) {
        i, ok := slices.BinarySearchFunc(loc, cod, func(l Localitate, c string) int {
            return cmp.Compare(l.Cod, c)
        })
        if ok {
            fmt.Println(cod, "->", loc[i].Nume)
        } else {
            fmt.Println(cod, "-> nu există, s-ar insera la", i)
        }
    }
    cauta("700001")
    cauta("500000")
}