"A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
A complexidade do algoritmo de Busca binária é da ordem de O(log n), em que n é o tamanho do
vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é O(n).
Dado uma lista Α de n elementos com os valores Α0, Α1,
Α2, ..., Αn-1 ordenada de tal modo que Α0 ≤
Α1 ≤ Α2 ≤ ... ≤ Αn-1, e um valor para pesquisa
T, a seguinte rotina usa pesquisa binária para achar o índice de T em Α.
- Defina
Lpara0eRparan - 1. - Se L > R a pesquisa termina sem sucesso.
- Defina
m(o índice do meio da lista) para(L + R) / 2arredondado. - Se Αm < T, defina
Lparam + 1e volte ao segundo passo. - Se Αm > T, defina
Rparam - 1e volte ao segundo passo. - Se Αm = T, a pesquisa está feita, o índice de
Tém.
Para o algoritmo computacional ser mais eficiente, foi implementado uma validação de Lista vazia, evitando-se a execução de procedimentos desnecessários!
./gradlew run
É possível observar que nem sempre a função nativa da linguagem
binarySearch()é a que possui a melhor performance!
Using only native kotlin.test and JUnit5.
./gradlew test