Sådan implementeres en binær søgealgoritme i Java uden rekursion

En iterativ implementering af den populære binære søgealgoritme til at finde et element i et sorteret array.

Hej allesammen! Jeg har offentliggjort mange algoritmer og datastrukturartikler på min blog, men denne er den første her. I denne artikel vil vi undersøge populære grundlæggende algoritmer til interviews.

Ja, du gættede det rigtigt: du skal implementere en binær søgning i Java, og du skal skrive både iterative og rekursive binære søgealgoritmer.

I datalogi er en binær søgning eller halvintervalssøgning en opdelings- og erobringsalgoritme, der lokaliserer placeringen af ​​et element i et sorteret array. Binær søgning fungerer ved at sammenligne en inputværdi med arrayets midterste element.

Sammenligningen bestemmer, om elementet er lig med input, er mindre end input eller er større end input.

Når elementet, der sammenlignes, er lig med input, stopper søgningen og returnerer typisk elementets position.

Hvis elementet ikke er lig med input, foretages der en sammenligning for at bestemme, om input er mindre end eller større end elementet.

Afhængigt af resultatet starter algoritmen derefter forfra, men søger kun i top- eller bundundersæt af arrayets elementer.

Hvis input ikke er placeret i arrayet, udsender algoritmen normalt en unik værdi, der angiver dette som -1 eller bare kaste en RuntimeException i Java som NoValueFoundException.

Binære søgealgoritmer halverer typisk antallet af emner, der skal kontrolleres med hver efterfølgende iteration, og lokaliserer således det givne element (eller bestemmer dets fravær) på logaritmisk tid.

Btw, hvis du ikke er fortrolig med grundlæggende algoritmer til søgning og sortering, kan du også deltage i et kursus som datastrukturer og algoritmer: dybdykning ved hjælp af Java til at lære grundlæggende algoritmer.

Hvis Java ikke er dit sprogvalg, kan du finde flere anbefalinger til JavaScript og Python i denne liste over algoritmekurser.

Btw, hvis du foretrækker bøger, foreslår jeg, at du læser en omfattende algoritmebog som Introduktion til algoritmer af Thomas H. Cormen.

Her er nogle eksempler på kode, der viser logikken i iterativ binær søgning i Java :

Implementering af binær søgning i Java

Her er et eksempelprogram til implementering af binær søgning i Java. Algoritmen implementeres rekursivt. En interessant kendsgerning at vide om implementering af binær søgning i Java er, at Joshua Bloch, forfatter af den berømte Effective Java-bog, skrev den binære søgning i “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.

Det handler om, hvordan man implementerer binær søgning ved hjælp af rekursion i Java . Sammen med lineær søgning er dette to af de vigtige søgealgoritmer, du lærer i din datalogiklasse.

Datastrukturen for binært søgetræ drager fordel af denne algoritme og arrangerer data i en hierarkisk struktur, så du kan søge i en hvilken som helst node i O (logN) -tid.

Selvom du skal huske, at du for at kunne bruge binær søgning har brug for en sorteret liste eller et array, så du skal også overveje omkostningerne ved sortering, når du overvejer at bruge binær søgealgoritme i den virkelige verden.

Videre læring

Datastrukturer og algoritmer: Dybdykning ved hjælp af Java

Algoritmer og datastrukturer - Del 1 og 2

Datastrukturer i Java 9 af Heinz Kabutz

10 algoritmebøger til interviews

10 Datastruktur- og algoritmekurser til interviews

5 gratis kurser for at lære datastruktur og algoritmer

Andre vejledninger i datastruktur og algoritmer, du måske kan lide

  • Hvordan implementeres Quicksort-algoritme på plads i Java? (tutorial)
  • Hvordan implementeres binært søgetræ i Java? (opløsning)
  • Hvordan implementeres Quicksort-algoritme uden rekursion? (tutorial)
  • Hvordan implementerer jeg sorteringsalgoritme i Java? (tutorial)
  • Hvordan implementeres Bubble sorteringsalgoritme i Java? (tutorial)
  • Hvad er forskellen mellem sammenlignings- og ikke-sammenligningsbaseret sorteringsalgoritme? (svar)
  • Sådan implementeres Bucket Sort i Java? (tutorial)
  • Hvordan implementeres en binær søgealgoritme uden rekursion i Java? (tutorial)
  • 50+ datastruktur- og algoritmekurser for programmører (spørgsmål)

Tak, fordi du læste denne artikel. Hvis du kan lide denne artikel, så del med dine venner og kolleger. Hvis du har forslag eller feedback, så send en kommentar.

PS - Hvis du er seriøs med at forbedre dine algoritmiske færdigheder, tror jeg, at datastrukturer og algoritmer: Deep Dive ved hjælp af Java er den bedste til at starte med.