Pesquisa em dados ordenados
Faça uma pesquisa binária
Pesquisa em dados ordenados é uma aula grátis de Go Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Go Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Go Academy inclui 4 aulas no total.
Por que pesquisar dados ordenados
Depois que uma fatia é ordenada, você pode localizar elementos muito mais rapidamente usando a pesquisa binária, em vez de verificar cada item.
O pacote sort do Go fornece auxiliares de pesquisa que são executados em tempo logarítmico.
Pesquisa linear versus binária
Uma pesquisa linear verifica cada elemento um por um (O(n)). A pesquisa binária reduz pela metade o intervalo de pesquisa a cada etapa (O(log n)), mas exige que os dados estejam ordenados primeiro.
sort.SearchInts
sort.SearchInts encontra o índice onde um valor está ou onde ele seria inserido para manter a fatia ordenada. A fatia já deve estar ordenada em ordem crescente.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7, 9}
i := sort.SearchInts(nums, 5)
fmt.Println("index:", i)
}Confirmando uma correspondência
SearchInts retorna um índice mesmo quando o valor está ausente, ou seja, o ponto de inserção. Confirme sempre verificando i < len(s) && s[i] == target.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7}
target := 4
i := sort.SearchInts(nums, target)
found := i < len(nums) && nums[i] == target
fmt.Println("index:", i, "found:", found)
}Ponto de inserção
Quando um valor está ausente, o índice retornado é exatamente onde você o inseriria para manter tudo ordenado. Neste caso, 4 ficaria no índice 2.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7}
i := sort.SearchInts(nums, 4)
fmt.Println("insert 4 at index:", i)
}SearchStrings
sort.SearchStrings faz o mesmo para uma fatia ordenada de cadeias de caracteres.
package main
import (
"fmt"
"sort"
)
func main() {
words := []string{"apple", "cherry", "mango"}
i := sort.SearchStrings(words, "cherry")
fmt.Println("index:", i)
}O sort.Search geral
sort.Search é o núcleo flexível. Você fornece um comprimento e uma função f que primeiro retorna false e depois true; ele retorna o menor índice em que f é verdadeira.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{2, 4, 6, 8, 10}
i := sort.Search(len(nums), func(i int) bool {
return nums[i] >= 6
})
fmt.Println("first >= 6 at index:", i)
}Localizar o primeiro elemento acima
Como sort.Search encontra o limite onde a condição muda para verdadeira, ele é excelente para consultas como localizar o primeiro valor maior que um limite.
package main
import (
"fmt"
"sort"
)
func main() {
scores := []int{10, 20, 30, 40}
i := sort.Search(len(scores), func(i int) bool {
return scores[i] > 25
})
fmt.Println("first > 25:", scores[i])
}É necessário ordenar primeiro
A pesquisa binária pressupõe uma ordem. Se a fatia não estiver ordenada, os resultados não terão sentido. Sempre ordene antes de pesquisar.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{9, 1, 5, 3}
sort.Ints(nums)
i := sort.SearchInts(nums, 5)
fmt.Println(nums, "-> index of 5:", i)
}Ganho de desempenho
Para uma fatia com um milhão de elementos, a pesquisa linear pode verificar um milhão de itens; a pesquisa binária verifica cerca de 20. O custo de ordenar uma vez compensa ao longo de muitas pesquisas.
Escolhendo um auxiliar de pesquisa
Resumo:
sort.SearchInts/SearchStrings/SearchFloat64s- fatias tipadassort.Search- condição personalizada sobre dados indexáveis de qualquer tipo
Verificação rápida
Você chama sort.SearchInts(s, 4) em uma fatia ordenada que não contém 4. O que é retornado?
Recapitulação
Pesquisando dados ordenados com pesquisa binária:
- Os dados devem ser ordenados primeiro
- Os auxiliares retornam um índice ou um ponto de inserção
- Confirme as correspondências com uma verificação de igualdade
sort.Searchlida com condições personalizadas
Perguntas Frequentes
A aula “Pesquisa em dados ordenados” é grátis?
Sim — o texto completo de “Pesquisa em dados ordenados” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Go Academy, atualize para CoddyKit PRO. O curso de Go Academy inclui 4 aulas no total.
O que vou aprender em “Pesquisa em dados ordenados”?
Faça uma pesquisa binária Você pratica Go Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Go Academy?
Nenhuma experiência prévia é necessária. Go Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Pesquisa em dados ordenados”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Go Academy?
Sim. Cada aula de Go Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Ordenação de slices
- Ordens de classificação personalizadas
- Pesquisa em dados ordenados
- Ordenação estável