Busca binária

A ideia

Só funciona com a lista ordenada. Compare o alvo com o elemento do meio: se for maior, ele só pode estar à direita; se for menor, à esquerda. Cada passo descarta metade, então o número de passos é log₂ n — O(log n).

Os erros clássicos

• (lo + hi) / 2 pode estourar o Int com listas enormes — o bug que ficou anos no Arrays.binarySearch do Java. Use lo + (hi − lo) / 2.
• Misturar intervalo fechado [lo, hi] com aberto [lo, hi): decida um e ajuste while (lo <= hi) e hi = meio − 1 de acordo.
• Esquecer de mover lo ou hi para além do meio e entrar em laço infinito.

Muito além de achar um número

Busca binária serve para achar o primeiro item que satisfaz uma condição (o primeiro dia com estoque zerado, o commit que quebrou o build com git bisect) e até para "chutar" a resposta de um problema numérico. Na prática, use binarySearch do Kotlin ou partitioningIndex do Swift Algorithms.

fun busca(a: IntArray, alvo: Int): Int {
    var lo = 0; var hi = a.size - 1
    while (lo < hi) {               // perde o caso lo == hi
        val meio = (lo + hi) / 2    // pode estourar o Int
        if (a[meio] < alvo) lo = meio else hi = meio // pode travar
    }
    return if (a[lo] == alvo) lo else -1 // quebra com array vazio
}

fun busca(a: IntArray, alvo: Int): Int {
    var lo = 0
    var hi = a.size - 1             // intervalo fechado [lo, hi]
    while (lo <= hi) {
        val meio = lo + (hi - lo) / 2
        when {
            a[meio] == alvo -> return meio
            a[meio] < alvo -> lo = meio + 1
            else -> hi = meio - 1
        }
    }
    return -1 // ou use a.binarySearch(alvo)
}