A pesquisa linear em Java sempre foi o método ideal para encontrar um elemento em uma matriz. Ele pesquisa cada elemento do array sequencialmente e é extremamente fácil de implementar. No entanto, as deficiências da Pesquisa Linear são óbvias quando o array em questão contém dezenas de milhares de elementos. Nesses casos, o método “dividir e conquistar” implementado pela Pesquisa Binária é muito mais eficiente e preferível para programadores com complexidade de tempo e espaço em mente.
Pesquisa binária
Na Busca Binária, um array é repetidamente dividido em duas metades até que a chave (elemento que está sendo buscado) seja encontrada. A divisão é virtual, ou seja, a integridade dos dados é mantida. Com cada iteração, o valor do meio da matriz é focado. Se o valor for igual à chave que estamos procurando, o loop ou função recursiva termina. Caso contrário, ele continua em loop. Se o valor do meio for maior que a chave, a função se concentrará na primeira metade da matriz e vice-versa. Esse processo é repetido até que a chave seja encontrada ou todo o array tenha sido iterado.
Diferença entre pesquisa linear e binária
Pesquisa Linear |
Pesquisa binária |
Pesquisa sequencialmente o array |
Divide a matriz em duas metades até que o valor seja encontrado |
Funciona com qualquer matriz |
Funciona apenas com matrizes classificadas |
Complexidade é O(N) |
Complexidade é O(log2N) |
Pode trabalhar em matrizes classificadas e não classificadas |
Só pode ser implementado em matrizes classificadas. |
Menos complexo de implementar |
Mais complexo de implementar |
Algoritmo de Pesquisa Binária
O algoritmo de busca binária é dado abaixo.
- Determine o primeiro e o último ponto da matriz. Os pontos serão ajustados a cada iteração de acordo com o array e a chave que está sendo pesquisada.
- Percorra a matriz e compare o valor intermediário entre o primeiro e o último pontos atuais. Na primeira iteração, a primeira e a última variável serão iguais às reais do array.
- Se a chave for maior que o valor do meio, o índice desse valor será armazenado na nova variável “First”.
- Se a chave for menor que o valor do meio, o índice desse valor será armazenado na variável 'Last'.
- Esta condição é repetida até que uma das duas condições se torne verdadeira:
- A chave foi encontrada.
- A matriz inteira foi iterada.
O código para pesquisa binária iterativa e pesquisa binária recursiva é fornecido abaixo.
Pesquisa Binária Iterativa
O código para pesquisa binária com um método iterativo é fornecido abaixo.
import java.util.Scanner;
public class IterativeBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchIterative(arr,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchIterative(int[] arr, int num){
int start = 0;
int end = arr.length;
for(int i = 0; iarr[n]){
start = n;
}
else{
end = n;
}
}
return -1;
}
}
Pesquisa Binária Recursiva
O código para Binário usando recursão é fornecido abaixo.
import java.util.Scanner;
public class RecursiveBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchRecursive(arr,0,arr.length-1,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
if(arr[n]==num)
return n;
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
else
return BinarySearchRecursive(arr,n+1,b,num);
}
}
Complexidade de tempo
A cada iteração que passa, o array, ou seja, o espaço de busca é dividido pela metade. Após cada iteração 'm', o espaço de busca mudará para um tamanho de N/2m. Na pior das hipóteses, ficaremos apenas com um elemento em um lado distante da matriz. Neste momento, a complexidade da busca binária será k = log2N. A complexidade de tempo da busca linear é O(N), o que resulta em uma busca binária muito mais rápida com a complexidade O(log2N). Esse é o principal benefício de usar a pesquisa binária em vez da pesquisa linear.
Complexidade Espacial
A pesquisa binária usa três variáveis diferentes — início, fim e meio. Essas três variáveis são criadas como ponteiros que apontam para a localização de memória dos índices do array. Devido a isso, a pesquisa binária é extremamente eficiente com o espaço. A complexidade espacial da busca binária iterativa é O(1). Para implementação recursiva, é O(log N).
GO TO FULL VERSION