Camada Zero · 02 · Busca Binária

Busca Binária em Go

func binarySearch(a []int, target int) int {
    lo, hi := 0, len(a)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2 // evita overflow
        switch {
        case a[mid] == target:
            return mid
        case a[mid] < target:
            lo = mid + 1
        default:
            hi = mid - 1
        }
    }
    return -1 // não encontrado
}

Na prática (stdlib)

// sort.SearchInts já faz isso, otimizado:
i := sort.SearchInts(a, target)
if i < len(a) && a[i] == target {
    // achou em i
}