A népszerű bináris keresési algoritmus iteratív megvalósítása egy elem megtalálásához egy rendezett tömbben.
Üdv mindenkinek! Nagyon sok algoritmust és adatszerkezeti cikket tettem közzé a blogomban, de ez itt az első. Ebben a cikkben megvizsgáljuk az interjúk népszerű alapvető algoritmusait.
Igen, jól sejtetted: bináris keresést kell végrehajtanod a Java-ban, és meg kell írnod iteratív és rekurzív bináris keresési algoritmusokat is.
A számítástechnikában a bináris keresés, vagy félintervallumos keresés egy megosztó és meghódító algoritmus, amely egy elem helyzetét rendezi egy rendezett tömbben. A bináris keresés úgy működik, hogy összehasonlítja a bemeneti értéket a tömb középső elemével.
Az összehasonlítás meghatározza, hogy az elem megegyezik-e a bemenettel, kisebb-e, mint a bemenet, vagy nagyobb-e, mint a bemenet.
Amikor az összehasonlítandó elem megegyezik a bemenettel, a keresés leáll, és általában visszaadja az elem helyzetét.
Ha az elem nem egyenlő a bemenettel, akkor összehasonlítással meghatározzuk, hogy a bemenet kisebb-e vagy nagyobb, mint az elem.
Az eredménytől függően az algoritmus ezután kezdődik elölről, de csak a tömb elemeinek felső vagy alsó részhalmazát keresi.
Ha a bemenet nem a tömbben található, akkor az algoritmus általában egyedi értéket ad ki, amely ezt jelzi, mint például -1, vagy csak egy RuntimeException-t dob a Java-ba, mint a NoValueFoundException.
A bináris keresési algoritmusok általában megfelezik az ellenőrzendő elemek számát minden egyes egymást követő iterációnál, így az adott elemet logaritmikus időben lokalizálják (vagy meghatározzák annak hiányát).
Btw, ha nem ismeri az alapvető keresési és rendezési algoritmusokat, akkor csatlakozhat egy olyan tanfolyamhoz is, mint az adatstruktúrák és algoritmusok: mély merülés a Java használatával az alapvető algoritmusok megtanulásához.
Ha a Java nem az Ön által választott nyelv, az algoritmusok tanfolyamainak listáján további javaslatokat talál a JavaScript és a Python használatához.
Btw, ha jobban szereted a könyveket, azt javaslom, hogy olvass el egy átfogó algoritmuskönyvet, például Thomas H. Cormen Bevezetés az algoritmusokba című könyvét .
Íme néhány példakód, amely az iteratív bináris keresés logikáját mutatja be a Java-ban :
Bináris keresés megvalósítása Java-ban
Itt van egy példa program a bináris keresés Java-ban történő megvalósítására. Az algoritmus rekurzív módon valósul meg. Szintén érdekes tény a bináris keresés Java-implementációjáról, hogy Joshua Bloch, a híres Effective Java könyv szerzője írta a bináris keresést a „java.util.Arrays” fájlban.
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.Ez csak arról szól, hogyan lehet bináris keresést megvalósítani rekurzióval a Java-ban . A lineáris kereséssel együtt ez a két alapvető keresési algoritmus, amelyet az informatika órán tanul.
A bináris keresőfa adatstruktúrája kihasználja ennek az algoritmusnak az előnyeit, és hierarchikus struktúrába rendezi az adatokat, így bármely csomópontban O (logN) idő alatt kereshet.
Ugyanakkor emlékeznie kell arra, hogy a bináris keresés használatához rendezett listára vagy tömbre van szüksége, ezért figyelembe kell vennie a rendezés költségeit is, amikor fontolóra veszi a bináris keresési algoritmus valós életben történő használatát.
További tanulás
Adatszerkezetek és algoritmusok: Mély merülés a Java használatával
Algoritmusok és adatszerkezetek - 1. és 2. rész
Data Structures in Java 9, Heinz Kabutz
10 algoritmuskönyv interjúkhoz
10 Adatszerkezet és algoritmus tanfolyamok interjúkhoz
5 ingyenes tanfolyam az adatszerkezet és az algoritmusok megismerésére
Egyéb adatszerkezet és algoritmusok oktatóanyagok , amelyek tetszhetnek
- Hogyan lehet megvalósítani a Quicksort algoritmust a Java-ban? (oktatóanyag)
- Hogyan lehet megvalósítani a bináris keresési fát a Java-ban? (megoldás)
- Hogyan valósítsuk meg a Quicksort algoritmust rekurzió nélkül? (bemutató)
- Hogyan lehet megvalósítani a Insertion sort algoritmust a Java-ban? (bemutató)
- 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.