Come implementare un algoritmo di ricerca binaria in Java senza ricorsione

Un'implementazione iterativa del popolare algoritmo di ricerca binaria per trovare un elemento in un array ordinato.

Ciao a tutti! Ho pubblicato molti algoritmi e articoli sulla struttura dei dati sul mio blog, ma questo è il primo qui. In questo articolo, esamineremo algoritmi fondamentali popolari per le interviste.

Sì, hai indovinato: devi implementare una ricerca binaria in Java e devi scrivere algoritmi di ricerca binaria sia iterativi che ricorsivi.

In informatica, una ricerca binaria, o ricerca a mezzo intervallo, è un algoritmo divide et impera che individua la posizione di un elemento in un array ordinato. La ricerca binaria funziona confrontando un valore di input con l'elemento centrale della matrice.

Il confronto determina se l'elemento è uguale all'input, è minore dell'input o è maggiore dell'input.

Quando l'elemento confrontato è uguale all'input, la ricerca si interrompe e in genere restituisce la posizione dell'elemento.

Se l'elemento non è uguale all'input, viene effettuato un confronto per determinare se l'input è minore o maggiore dell'elemento.

A seconda del risultato, l'algoritmo ricomincia da capo, ma cerca solo il sottoinsieme superiore o inferiore degli elementi dell'array.

Se l'input non si trova all'interno dell'array, l'algoritmo di solito restituisce un valore univoco che lo indica come -1 o genera semplicemente una RuntimeException in Java come NoValueFoundException.

Gli algoritmi di ricerca binaria tipicamente dimezzano il numero di elementi da controllare ad ogni iterazione successiva, individuando così l'elemento dato (o determinandone l'assenza) nel tempo logaritmico.

A proposito, se non hai familiarità con gli algoritmi di ricerca e ordinamento fondamentali, puoi anche partecipare a un corso come Strutture dati e algoritmi: Deep Dive Using Java per apprendere gli algoritmi fondamentali.

Se Java non è la tua scelta di linguaggio, puoi trovare ulteriori consigli per JavaScript e Python in questo elenco di corsi sugli algoritmi.

A proposito, se preferisci i libri, ti suggerisco di leggere un libro completo di algoritmi come Introduzione agli algoritmi di Thomas H. Cormen.

Ecco un codice di esempio che mostra la logica della ricerca binaria iterativa in Java :

Implementazione della ricerca binaria in Java

Ecco un programma di esempio per implementare la ricerca binaria in Java. L'algoritmo è implementato in modo ricorsivo. Inoltre, un fatto interessante da sapere sull'implementazione della ricerca binaria in Java è che Joshua Bloch, autore del famoso libro Effective Java, ha scritto la ricerca binaria in "java.util.Arrays".

import java.util.Arrays;import java.util.Scanner;
/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/
public class IterativeBinarySearch {
 public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list));
 binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333);
 // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list);
 // Search an element int index = Arrays.binarySearch(list, 3);
}
/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */
public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;
while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {
System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}
middle = (first + last) / 2;
}
if (first > last) { System.out.println(number + " is not present in the list.\n");}
}
}
OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.

Questo è tutto su come implementare la ricerca binaria utilizzando la ricorsione in Java . Insieme alla ricerca lineare, questi sono due degli algoritmi di ricerca essenziali che impari durante il corso di informatica.

La struttura dei dati dell'albero di ricerca binaria sfrutta questo algoritmo e dispone i dati in una struttura gerarchica in modo da poter cercare qualsiasi nodo nel tempo O (logN).

Tuttavia, è necessario ricordare che per utilizzare la ricerca binaria, è necessario un elenco o un array ordinato, quindi è necessario considerare anche il costo dell'ordinamento quando si considera l'utilizzo dell'algoritmo di ricerca binaria nel mondo reale.

Apprendimento ulteriore

Strutture dati e algoritmi: Deep Dive Using Java

Algoritmi e strutture dati - Parte 1 e 2

Strutture dati in Java 9 di Heinz Kabutz

10 libri di algoritmi per interviste

10 Corsi di struttura dei dati e algoritmi per le interviste

5 corsi gratuiti per apprendere la struttura dei dati e gli algoritmi

Altre esercitazioni sulla struttura dei dati e sugli algoritmi che potrebbero piacerti

  • Come implementare l'algoritmo Quicksort in posizione in Java? (tutorial)
  • Come implementare l'albero di ricerca binario in Java? (soluzione)
  • Come implementare l'algoritmo Quicksort senza ricorsione? (tutorial)
  • Come implementare l'algoritmo di ordinamento per inserimento in Java? (tutorial)
  • How to implement Bubble sort algorithm in Java? (tutorial)
  • What is the difference between Comparison and Non-Comparison based sorting algorithm? (answer)
  • How to implement Bucket Sort in Java? (tutorial)
  • How to implement a Binary Search Algorithm without recursion in Java? (tutorial)
  • 50+ Data Structure and Algorithms Courses for Programmers (questions)

Thanks for reading this article. If you like this article then please share with your friends and colleagues. If you have any suggestion or feedback then please drop a comment.

P.S. — If you are serious about improving your Algorithms skills, I think the Data Structures and Algorithms: Deep Dive Using Java is the best one to start with.