binary search algorithm java implementation examples
Este tutorial explicará a pesquisa binária e a pesquisa binária recursiva em Java, juntamente com seu algoritmo, implementação e exemplos de código de pesquisa binária Java:
Uma pesquisa binária em Java é uma técnica usada para pesquisar um valor ou chave de destino em uma coleção. É uma técnica que usa a técnica de “dividir para conquistar” para buscar uma chave.
A coleção na qual a pesquisa binária deve ser aplicada para pesquisar uma chave precisa ser classificada em ordem crescente.
Normalmente, a maioria das linguagens de programação oferece suporte para pesquisa linear, pesquisa binária e técnicas de hash que são usadas para pesquisar dados na coleção. Aprenderemos o hash em nossos tutoriais subsequentes.
=> Visite aqui para aprender Java do zero.
O que você aprenderá:
Pesquisa binária em Java
A pesquisa linear é uma técnica básica. Nesta técnica, o array é percorrido sequencialmente e cada elemento é comparado à chave até que a chave seja encontrada ou o final do array seja alcançado.
A pesquisa linear raramente é usada em aplicações práticas. A pesquisa binária é a técnica usada com mais frequência, pois é muito mais rápida do que uma pesquisa linear.
Java oferece três maneiras de realizar uma pesquisa binária:
como executo um arquivo jar
- Usando a abordagem iterativa
- Usando uma abordagem recursiva
- Usando o método Arrays.binarySearch ().
Neste tutorial, implementaremos e discutiremos todos esses três métodos.
Algoritmo para pesquisa binária em Java
No método de pesquisa binária, a coleção é repetidamente dividida na metade e o elemento-chave é pesquisado na metade esquerda ou direita da coleção, dependendo se a chave é menor ou maior que o elemento intermediário da coleção.
Um algoritmo de pesquisa binária simples é o seguinte:
- Calcule o elemento médio da coleção.
- Compare os itens principais com o elemento intermediário.
- Se chave = elemento do meio, então retornamos a posição do índice médio para a chave encontrada.
- Else If key> mid element, então a chave está na metade direita da coleção. Portanto, repita as etapas 1 a 3 na metade inferior (direita) da coleção.
- Outra chave
Como você pode ver nas etapas acima, na pesquisa binária, metade dos elementos da coleção são ignorados logo após a primeira comparação.
Observe que a mesma sequência de etapas vale para pesquisa binária iterativa e recursiva.
Vamos ilustrar o algoritmo de pesquisa binária usando um exemplo.
Por exemplo, pegue a seguinte matriz classificada de 10 elementos.
Vamos calcular a localização do meio da matriz.
Médio = 0 + 9/2 = 4
# 1) Chave = 21
Primeiro, compararemos o valor-chave com o elemento [mid] e descobrimos que o valor do elemento em mid = 21.
Assim, encontramos essa chave = [mid]. Portanto, a chave é encontrada na posição 4 na matriz.
# 2) Chave = 25
Primeiro, comparamos o valor-chave com o meio. Como (21<25), we will directly search for the key in the upper half of the array.
como implementar lista duplamente vinculada em java
Agora, novamente, encontraremos o meio para a metade superior da matriz.
Médio = 4 + 9/2 = 6
O valor no local [mid] = 25
Agora comparamos o elemento-chave com o elemento médio. Então (25 == 25), portanto, encontramos a chave no local [mid] = 6.
Assim, dividimos repetidamente o array e, comparando o elemento-chave com o meio, decidimos em qual metade procurar a chave. A pesquisa binária é mais eficiente em termos de tempo e correção e é muito mais rápida também.
Implementação de pesquisa binária Java
Usando o algoritmo acima, vamos implementar um programa de pesquisa binária em Java usando a abordagem iterativa. Neste programa, pegamos um array de exemplo e realizamos uma pesquisa binária neste array.
import java.util.*; class Main{ public static void main(String args[]){ int numArray[] = {5,10,15,20,25,30,35}; System.out.println('The input array: ' + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println('
Key to be searched=' + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //calculate mid of the array int mid = (first + last)/2; //while first and last do not overlap while( first <= last ){ //if the mid < key, then key to be searched is in the first half of array if ( numArray[mid] last ){ System.out.println('Element is not found!'); } } }
Resultado:
A matriz de entrada: [5, 10, 15, 20, 25, 30, 35]
Chave a ser pesquisada = 20
O elemento é encontrado no índice: 3
O programa acima mostra uma abordagem iterativa da pesquisa binária. Inicialmente, um array é declarado e, em seguida, uma chave a ser pesquisada é definida.
Depois de calcular o meio do array, a chave é comparada ao elemento do meio. Então, dependendo se a chave é menor ou maior que a chave, a chave é pesquisada na metade inferior ou superior da matriz, respectivamente.
Pesquisa binária recursiva em Java
Você também pode realizar uma pesquisa binária usando a técnica de recursão. Aqui, o método de pesquisa binária é chamado recursivamente até que a chave seja encontrada ou toda a lista se esgote.
O programa que implementa uma pesquisa binária recursiva é fornecido abaixo:
import java.util.*; class Main{ //recursive method for binary search public static int binary_Search(int intArray[], int low, int high, int key){ //if array is in order then perform binary search on the array if (high>=low){ //calculate mid int mid = low + (high - low)/2; //if key =intArray[mid] return mid if (intArray[mid] == key){ return mid; } //if intArray[mid] > key then key is in left half of array if (intArray[mid] > key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of the array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } } return -1; } public static void main(String args[]){ //define array and key int intArray[] = {1,11,21,31,41,51,61,71,81,91}; System.out.println('Input List: ' + Arrays.toString(intArray)); int key = 31; System.out.println('
The key to be searched:' + key); int high=intArray.length-1; //call binary search method int result = binary_Search(intArray,0,high,key); //print the result if (result == -1) System.out.println('
Key not found in given list!'); else System.out.println('
Key is found at location: '+result + ' in the list'); } }
Resultado:
Lista de entrada: [1, 11, 21, 31, 41, 51, 61, 71, 81, 91
A chave a ser pesquisada:
A chave é encontrada no local: 3 na lista
Usando o método Arrays.binarySearch ().
A classe Arrays em Java fornece um método ‘binarySearch ()’ que realiza a pesquisa binária no Array fornecido. Este método usa o array e a chave a serem pesquisados como argumentos e retorna a posição da chave no array. Se a chave não for encontrada, o método retornará -1.
O exemplo a seguir implementa o método Arrays.binarySearch ().
melhor spyware de celular para android
import java.util.Arrays; class Main{ public static void main(String args[]){ //define an array int intArray[] = {10,20,30,40,50,60,70,80,90}; System.out.println('The input Array : ' + Arrays.toString(intArray)); //define the key to be searched int key = 50; System.out.println('
The key to be searched:' + key); //call binarySearch method on the given array with key to be searched int result = Arrays.binarySearch(intArray,key); //print the return result if (result <0) System.out.println('
Key is not found in the array!'); else System.out.println('
Key is found at index: '+result + ' in the array.'); } }
Resultado:
A matriz de entrada: [10, 20, 30, 40, 50, 60, 70, 80, 90]
A chave a ser pesquisada: 50
A chave é encontrada no índice: 4 na matriz.
perguntas frequentes
P # 1) Como você escreve uma pesquisa binária?
Responda: A pesquisa binária é geralmente realizada dividindo a matriz em metades. Se a chave a ser pesquisada for maior do que o elemento do meio, então a metade superior da matriz é pesquisada dividindo e pesquisando a submatriz até que a chave seja encontrada.
Da mesma forma, se a chave for menor que o elemento do meio, a chave é pesquisada na metade inferior da matriz.
P # 2) Onde a pesquisa binária é usada?
Responda: A pesquisa binária é usada principalmente para pesquisar dados classificados em aplicativos de software, especialmente quando o espaço de memória é compacto e limitado.
P # 3) Qual é o grande O da pesquisa binária?
Responda: A complexidade de tempo da pesquisa binária é O (logn), onde n é o número de elementos no array. A complexidade espacial da busca binária é O (1).
P # 4) A pesquisa binária é recursiva?
Responda: sim. Uma vez que a pesquisa binária é um exemplo de estratégia de dividir e conquistar e pode ser implementada usando recursão. Podemos dividir o array em metades e chamar o mesmo método para realizar a pesquisa binária repetidas vezes.
P # 5) Por que é chamada de pesquisa binária?
Responda: O algoritmo de pesquisa binária usa uma estratégia de divisão e conquista que corta repetidamente a matriz em metades ou duas partes. Portanto, é chamada de pesquisa binária.
Conclusão
A pesquisa binária é a técnica de pesquisa frequentemente usada em Java. O requisito para que uma pesquisa binária seja realizada é que os dados sejam classificados em ordem crescente.
Uma pesquisa binária pode ser implementada usando uma abordagem iterativa ou recursiva. A classe Arrays em Java também fornece o método ‘binarySearch’ que realiza uma pesquisa binária em um Array.
Em nossos tutoriais subsequentes, exploraremos várias técnicas de classificação em Java.
=> Veja a série de treinamento simples em Java aqui.
Leitura recomendada
- Classificação de seleção em Java - Algoritmo de classificação de seleção e exemplos
- Insertion Sort In Java - Insertion Sort Algorithm & Exemplos
- Árvore de pesquisa binária C ++: implementação e operações BST com exemplos
- Interface Java e tutorial de classe abstrata com exemplos
- Tutorial JAVA para iniciantes: mais de 100 tutoriais práticos em vídeo Java
- Bubble Sort In Java - Algoritmos de classificação Java e exemplos de código
- Tutorial de Java String | Métodos Java String com exemplos
- O que é Java Vector | Tutorial da classe Java Vector com exemplos