Este titorial explicará a busca binaria e amp; Busca binaria recursiva en Java xunto co seu algoritmo, implementación e exemplos de código binario de busca de Java:
Unha busca binaria en Java é unha técnica que se usa para buscar un valor ou clave de destino nunha colección. É unha técnica que utiliza a técnica "divide e vencerás" para buscar unha clave.
A colección na que se aplicará a busca binaria para buscar unha clave debe ordenarse en orde ascendente.
Normalmente, a maioría das linguaxes de programación admiten técnicas de busca lineal, busca binaria e hash que se usan para buscar datos na colección. Aprenderemos hash nos nosos titoriais posteriores.
Busca binaria en Java
A busca lineal é unha técnica básica. Nesta técnica, a matriz percorrese secuencialmente e cada elemento compárase coa clave ata que se atopa a clave ou se chega ao final da matriz.
A busca lineal úsase raramente en aplicacións prácticas. A busca binaria é a técnica máis utilizada xa que é moito máis rápida que unha busca lineal.
Java ofrece tres formas de realizar unha busca binaria:
- Utilizando o enfoque iterativo
- Uso dun enfoque recursivo
- Uso do método Arrays.binarySearch ().
Neste titorial, implementaremos e discutiremos todos estes 3 métodos.
Algoritmo para a busca binaria en Java
No binariométodo de busca, a colección divídese repetidamente á metade e o elemento clave búscase na metade esquerda ou dereita da colección, dependendo de se a clave é menor ou maior que o elemento central da colección.
Un algoritmo de busca binario sinxelo é o seguinte:
- Calcula o elemento medio da colección.
- Compare os elementos clave co elemento central.
- Se chave = elemento central, entón devolvemos a posición do índice medio para a chave atopada.
- Se non, se chave > elemento medio, entón a clave está na metade dereita da colección. Así, repita os pasos do 1 ao 3 na metade inferior (dereita) da colección.
- Tecla Else elemento medio, entón a clave está na metade superior da colección. Polo tanto, cómpre repetir a busca binaria na metade superior.
Como podes ver nos pasos anteriores, na busca binaria ignóranse a metade dos elementos da colección xusto despois da primeira comparación.
Teña en conta que a mesma secuencia de pasos vale para a busca binaria iterativa e recursiva.
Ilustremos o algoritmo de busca binaria usando un exemplo.
Por exemplo, tome a seguinte matriz ordenada de 10 elementos.
Calculemos a localización media da matriz.
Mid = 0+9/2 = 4
#1) Tecla = 21
Primeiro, compararemos o valor da clave co [mid] elemento e atopamos que o elemento valor enmid = 21.
Así atopamos esa clave = [mid]. Polo tanto, a clave atópase na posición 4 da matriz.
#2) Chave = 25
Primeiro comparamos a clave valor a medio. Como (21 25), buscaremos directamente a chave na metade superior da matriz.
Agora de novo atoparemos o medio para a metade superior da matriz. a matriz.
Mid = 4+9/2 = 6
O valor na localización [mid] = 25
Agora compara o elemento clave co elemento medio. Entón (25 == 25), polo tanto atopamos a clave na localización [mid] = 6.
Así dividimos repetidamente a matriz e comparando o elemento clave co medio, decidimos en que metade buscar a chave. A busca binaria é máis eficiente en termos de tempo e corrección e tamén é moito máis rápida.
Implementación de busca binaria Java
Utilizando o algoritmo anterior, imos implementar un programa de busca binaria en Java usando o enfoque iterativo. Neste programa, tomamos unha matriz de exemplo e realizamos unha busca binaria nesta matriz.
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("\nKey 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!"); } } }
Saída:
A matriz de entrada: [5, 10, 15, 20 , 25, 30, 35]
Clave a buscar=20
O elemento atópase no índice: 3
O programa anterior mostra un enfoque iterativo da busca binaria. Inicialmente, declárase unha matriz, despois defínese unha clave para buscar.
Despois de calcular o medio da matriz, a chave compárase co elemento medio. Despois segundo sea chave é menor ou maior que a chave, a clave búscase na metade inferior ou superior da matriz, respectivamente.
Busca binaria recursiva En Java
Tamén pode realizar unha busca binaria utilizando a técnica de recursividade. Aquí, o método de busca binario chámase recursivamente ata que se atopa a chave ou se esgota a lista completa.
O programa que implementa unha busca binaria recursiva indícase a continuación:
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("\nThe 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("\nKey not found in given list!"); else System.out.println("\nKey is found at location: "+result + " in the list"); } }
Saída:
Lista de entradas: [1, 11, 21, 31, 41, 51, 61, 71, 81, 91
A chave a buscar :
A chave atópase na localización: 3 da lista
Usando o método Arrays.binarySearch ().
A clase Arrays en Java proporciona un método ‘binarySearch ()’ que realiza a busca binaria na matriz dada. Este método toma a matriz e a clave a buscar como argumentos e devolve a posición da clave na matriz. Se non se atopa a chave, entón o método devolve -1.
O seguinte exemplo implementa o método Arrays.binarySearch ().
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("\nThe 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("\nKey is not found in the array!"); else System.out.println("\nKey is found at index: "+result + " in the array."); } }
Saída:
A matriz de entrada: [10, 20, 30, 40, 50, 60, 70, 80, 90]
A clave que se vai buscar:50
A clave atópase no índice: 4 na matriz.
Preguntas máis frecuentes
P #1) Como se escribe unha busca binaria ?
Resposta: A busca binaria adoita realizarse dividindo a matriz en metades. Se a clave a buscar é maior que o elemento medio,entón búscase na metade superior da matriz dividindo e buscando a submatriz ata atopar a chave.
Do mesmo xeito, se a chave é menor que o elemento medio, a chave buscarase na parte inferior. metade da matriz.
P #2) Onde se usa a busca binaria?
Resposta: A busca binaria utilízase principalmente para buscar unha datos ordenados en aplicacións de software, especialmente cando o espazo de memoria é compacto e limitado.
P #3) Cal é o gran O da busca binaria?
Resposta : A complexidade temporal da busca binaria é O (logn) onde n é o número de elementos da matriz. A complexidade espacial da busca binaria é O (1).
Q #4) A busca binaria é recursiva?
Resposta: Si. Xa que a busca binaria é un exemplo dunha estratexia dividir e vencer e pódese implementar mediante recursión. Podemos dividir a matriz en metades e chamar ao mesmo método para realizar a busca binaria unha e outra vez.
P #5) Por que se chama busca binaria?
Resposta: O algoritmo de busca binaria usa unha estratexia de división e conquista que corta repetidamente a matriz en metades ou dúas partes. Así, chámase como busca binaria.
Conclusión
A busca binaria é a técnica de busca que se usa con frecuencia en Java. O requisito para realizar unha busca binaria é que os datos se clasifiquen en orde ascendente.
Unha busca binaria pode serimplementado mediante un enfoque iterativo o recursivo. A clase Arrays en Java tamén proporciona o método 'binarySearch' que realiza unha busca binaria nunha matriz.
Nos nosos titoriais posteriores, exploraremos varias técnicas de clasificación en Java.