Kuidas rakendada Java-s binaarotsingu algoritmi ilma rekursioonita

Populaarse binaarotsingu algoritmi iteratiivne rakendamine sorditud massiivi elemendi leidmiseks.

Tere kõigile! Olen oma ajaveebis avaldanud palju algoritme ja andmestruktuuriartikleid, kuid see on siin esimene. Selles artiklis uurime intervjuude jaoks populaarseid põhialgoritme.

Jah, arvasite õigesti: peate Java-s rakendama binaarotsingu ja peate kirjutama nii iteratiivsed kui ka rekursiivsed binaarotsingu algoritmid.

Arvutiteaduses on binaarotsing ehk poolintervallotsing jagamise ja vallutamise algoritm, mis määrab üksuse asukoha sorteeritud massiivis. Binaarotsing toimib sisendväärtuse võrdlemisel massiivi keskmise elemendiga.

Võrdlus määrab, kas element võrdub sisendiga, on väiksem kui sisend või on suurem kui sisend.

Kui võrreldav element võrdub sisendiga, siis otsing peatub ja tavaliselt tagastab elemendi asukoha.

Kui element pole sisendiga võrdne, võrreldakse, kas sisend on elemendist väiksem või suurem.

Sõltuvalt tulemusest algab algoritm uuesti otsast, kuid otsib ainult massiivi elementide ülemist või alumist alamhulka.

Kui sisend ei asu massiivi sees, väljastab algoritm tavaliselt kordumatu väärtuse, mis näitab seda nagu -1, või viskab lihtsalt Java-sse RuntimeExceptioni nagu NoValueFoundException.

Binaarotsingu algoritmid poolitavad iga järgneva iteratsiooni korral kontrollitavate üksuste arvu tavaliselt poole võrra, määrates nii antud elemendi (või määrates selle puudumise) logaritmilises ajas.

Btw, kui te pole põhiliste otsingu- ja sorteerimisalgoritmidega kursis, võite liituda ka kursustega nagu Andmestruktuurid ja Algoritmid: Süvaveesüsteem Java kasutamise abil algoritmide õppimiseks.

Kui Java pole teie valitud keel, leiate sellest algoritmikursuste loendist veel JavaScripti ja Pythoni soovitusi.

Btw, kui eelistate raamatuid, soovitan teil lugeda põhjalikku algoritmiraamatut, nagu Thomas H. Cormeni sissejuhatus algoritmidesse .

Siin on mõned näidiskoodid, mis näitavad Java iteratiivse binaarotsingu loogikat :

Binaarotsingu juurutamine Java-s

Siin on näidisprogramm Java-binaarotsingu rakendamiseks. Algoritmi rakendatakse rekursiivselt. Huvitav fakt, mida on vaja teada Java-binaarotsingu juurutamisest, on see, et kuulsa Effective Java raamatu autor Joshua Bloch kirjutas kahendotsingu kausta „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.

See kõik käib selle kohta, kuidas kahendotsingut juurutada Java-s rekursiooni abil . Koos lineaarse otsinguga on need kaks olulist otsingualgoritmi, mida õpite oma arvutiteaduse tunnis.

Binaarotsingupuu andmestruktuur kasutab seda algoritmi ära ja korraldab andmed hierarhilises struktuuris, nii et saate otsida mis tahes sõlme O (logN) aja jooksul.

Though, you must remember that in order to use binary search, you need a sorted list or array, so you also need to consider the cost of sorting when you consider using binary search algorithm in the real world.

Further Learning

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures — Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

10 Algorithms books for Interviews

10 Data Structure and Algorithm Courses for Interviews

5 Free Courses to Learn Data Structure and Algorithms

Other Data Structure and Algorithms tutorials you may like

  • How to implement Quicksort algorithm in place in Java? (tutorial)
  • How to implement Binary Search Tree in Java? (solution)
  • How to implement Quicksort algorithm without recursion? (tutorial)
  • How to implement Insertion sort algorithm in Java? (tutorial)
  • Kuidas rakendada Java-s mullide sorteerimise algoritmi? (juhendaja)
  • Mis vahe on võrdlus- ja mittepõhisel sortimisalgoritmil? (vastus)
  • Kuidas rakendada Bucket Sort Java-s? (juhendaja)
  • Kuidas rakendada Java-s rekursioonita kahendotsingu algoritmi? (juhendaja)
  • 50+ andmekonstruktsiooni ja algoritmide kursust programmeerijatele (küsimused)

Täname selle artikli lugemise eest. Kui teile see artikkel meeldib, jagage palun oma sõprade ja kolleegidega. Kui teil on ettepanekuid või tagasisidet, siis palun kommenteerige.

PS - kui soovite tõsiselt oma algoritmide oskusi täiendada, arvan, et kõige parem on alustada andmekonstruktsioonide ja algoritmide kasutamist: Java sügav kasutamine.