Skip to content

chinnonsantos/binary-search-in-kotlin

Repository files navigation

Kotlin Logo

Binary Search in Kotlin (JVM) - Console Application

"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.

-- Pesquisa Binária - Wikipedia

binary-x-linear-search binary-search-tree

Dependencies

Complexity Analysis

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).

Procedure

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 Α.

  1. Defina L para 0 e R para n - 1.
  2. Se L > R a pesquisa termina sem sucesso.
  3. Defina m(o índice do meio da lista) para (L + R) / 2 arredondado.
  4. Se Αm < T, defina L para m + 1 e volte ao segundo passo.
  5. Se Αm > T, defina R para m - 1 e volte ao segundo passo.
  6. 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!

How to run?

./gradlew run

With empty list

image

With a search lower than list

image

image

With a search higher than the list

image

image

With a random search

image

image

image

image

É possível observar que nem sempre a função nativa da linguagem binarySearch() é a que possui a melhor performance!

How to test?

Using only native kotlin.test and JUnit5.

./gradlew test

About

Algoritmo de busca binária em linguagem Kotlin

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages