English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
In questo esempio, impareremo a implementare l'algoritmo di ricerca binaria in Java.
Prima di implementare la ricerca binaria in Java, assicurati di comprendere il funzionamento dell'algoritmo di ricerca binaria.
import java.util.Scanner;
// Ricerca binaria in Java
class Main {
int binarySearch(int array[], int element, int low, int high) {
// Ripetere questo processo fino a quando i puntatori alto (high) e basso (low) sono uguali
while (low <= high) {
// Ottenere l'indice dell'elemento mid
int mid = low + (high - low) / 2;
// Se l'elemento da cercare è l'elemento mid
if (array[mid] == element)
return mid;
// Se l'elemento è minore dell'elemento mid
// Solo cercare a sinistra di mid
if (array[mid] < element)
low = mid + 1;
// Se l'elemento è maggiore dell'elemento mid
// Solo cercare a destra di mid
else
high = mid - 1;
{}
return -1;
{}
public static void main(String args[]) {
// Creare un oggetto della classe Main
Main obj = new Main();
// Creare un array ordinato
int[] array = {3, 4, 5, 6, 7, 8, 9};
int n = array.length;
// Riceviamo l'input dall'utente, elemento da cercare
Scanner input = new Scanner(System.in);
System.out.println("Inserisci l'elemento da cercare:");
// Elemento da cercare
int element = input.nextInt();
input.close();
// Chiamare il metodo di ricerca binaria
// Passare i parametri: array, elemento, l'indice del primo e dell'ultimo elemento
int result = obj.binarySearch(array, element, 0, n - 1);
if (result == -1)
System.out.println("Non trovato");
else
System.out.println("Trovato l'elemento, all'indice " + result);
{}
{}Output 1
Inserisci l'elemento da cercare: 6 Trovato l'elemento, all'indice 3
Qui, abbiamo già utilizzatoClasse scanner JavaRiceviamo l'input dall'utente. Secondo l'input dell'utente, abbiamo utilizzato la ricerca binaria per verificare se l'elemento esiste nell'array.
Possiamo ancora utilizzare la chiamata ricorsiva per eseguire la stessa attività.
int binarySearch(int array[], int element, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
//Verifica se l'elemento mid è l'elemento da cercare
if (array[mid] == element)
return mid;
//Cerca la metà sinistra di mid
if (array[mid] > element)
return binarySearch(array, element, low, mid - 1);
//Cerca la metà destra di mid
return binarySearch(array, element, mid + 1, high);
{}
return -1;
{}In questo caso, il metodo binarySearch() chiamerà se stesso fino a trovare l'elemento o il fallimento della condizione if.