English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Neste exemplo, vamos aprender a implementar o algoritmo de busca binária em Java.
Antes de aprender a implementação da busca binária em Java, certifique-se de que você entende o funcionamento do algoritmo de busca binária.
import java.util.Scanner; //Busca binária em Java class Main { int binarySearch(int array[], int elemento, int baixo, int alto) { //Repetir este processo até que o ponteiro alto (high) e baixo (low) sejam iguais while (low <= high) { //Obter o índice do elemento mid int meio = baixo + (alto - baixo) / 2; //Se o elemento a ser pesquisado for o elemento mid if (array[meio] == elemento) return meio; //Se o elemento for menor que o elemento mid //Somente pesquisar o lado esquerdo de mid if (array[mid] < element) low = mid + 1; //Se o elemento for maior que o elemento mid //Somente pesquisar o lado direito de mid else high = mid - 1; } return -1; } public static void main(String args[]) { //Criar um objeto da classe Main Main obj = new Main(); //Criar um array ordenado int[] array = { 3, 4, 5, 6, 7, 8, 9 }; int n = array.length; //Obter entrada do usuário, elemento a ser pesquisado Scanner input = new Scanner(System.in); System.out.println("Insira o elemento a ser pesquisado:"); //Elemento a ser pesquisado int element = input.nextInt(); input.close(); //Chamar o método de busca binária //Passar os parâmetros: array, elemento, índice do primeiro e último elementos int result = obj.binarySearch(array, element, 0, n - 1); if (result == -1) System.out.println("Não encontrado"); else System.out.println("Encontrar o elemento, na índice " + result); } }
Saída1
Insira o elemento a ser pesquisado: 6 Encontrar o elemento, na índice 3
Aqui, já usamosClasse Scanner JavaObter entrada do usuário. De acordo com a entrada do usuário, usamos a busca binária para verificar se o elemento existe no array.
Também podemos usar chamadas recursivas para executar a mesma tarefa.
int binarySearch(int array[], int elemento, int baixo, int alto) { if (alto >= baixo) { int meio = baixo + (alto - baixo) / 2; // Verificar se o elemento meio é o elemento procurado if (array[meio] == elemento) return meio; //Procurar a metade esquerda de meio if (array[meio] > elemento) return binarySearch(array, elemento, baixo, meio - 1); //Procurar a metade direita de meio return binarySearch(array, elemento, meio + 1, alta); } return -1; }
Aqui, o método binarySearch() será chamado recursivamente até encontrar o elemento ou até a condição if falhar.