Søge- og sorteringsalgoritmer er populære algoritmer på ethvert programmeringssprog. De er grundlaget for at forstå det grundlæggende i programmeringen. En sådan populær søgealgoritme er Binær søgning i . I denne artikel vil jeg fortælle dig alt om dens implementering.
Nedenstående emner er dækket af denne artikel:
Lad os komme igang!
Hvad er binær søgning?
Binær søgning i er en søgealgoritme, der finder placeringen af en målværdi inden for en sorteret array . Binær søgning sammenligner målværdien med matrixens midterste element. Detfungerer kun på et sorteret sæt af elementer. Hvis du vil bruge binær søgning på en samling, skal skal først sorteres.
Når bruges til at udføre operationer på et sorteret sæt, kan antallet af iterationer altid reduceres på baggrund af den værdi, der søges efter. Du kan se i ovenstående øjebliksbillede af at finde midt element . Analogien med binær søgning er at bruge de oplysninger, som arrayet er sorteret og reducere tidskompleksiteten til O (log n) .
Implementering af binær søgealgoritme
Lad os se på nedenstående pseudokode for at forstå det på en bedre måde.
Procedure binary_search A & larr sorteret array n & larr størrelse af array x & larr værdi, der skal søges Indstil lav = 1 Indstil høj = n, mens x ikke findes, hvis højForklaring:
Trin 1: Sammenlign først x med det midterste element.
Trin 2: Hvis x stemmer overens med det midterste element, skal du returnere midtindekset.
Trin 3: Ellers, hvis x er større end midterelementet, kan x kun ligge i højre halvterray efter midterelementet. Derfor gentager du den højre halvdel.
Trin 4: Ellers, hvis (x er mindre), gentager du den venstre halvdel.
Sådan skal du søge efter elementet i det givne array.
c ++ program for at sortere en matrix i stigende rækkefølgeLad os nu se, hvordan man implementerer en binær søgealgoritme rekursivt. Nedenstående program viser det samme.
Rekursiv binær søgning
offentlig klasse BinarySearch {// Java-implementering af rekursiv binær søgning // Returnerer indeks på x, hvis det er til stede i arr [l..h], ellers returnerer -1 int binærsøgning (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Hvis elementet er til stede i selve midten, hvis (a [mid] == x) returnerer mid // Hvis element er mindre end midt, så kan den kun være til stede i venstre subarray, hvis (a [mid]> x) return binærsøgning (arr, l, mid - 1, x) // Ellers kan elementet kun være til stede i højre subarray return binærSearch (arr, mid + 1, h, x)} // Vi når her, når elementet ikke er til stede i array-retur -1} public static void main (String args []) {BinarySearch ob = new BinarySearch () int a [] = {20, 30, 40, 10, 50} int n = a. Længde int x = 40 int res = ob.binarySearch (a, 0, n - 1, x) hvis (res == -1) System.out .println ('Element ikke til stede') ellers System.out.println ('Element fundet ved indeks' + res)}}Ved udførelse af ovenstående program finder den det element, der findes i det bestemte indeks
Element fundet ved indeks 2Så dette bringer os til slutningen af den binære søgning i Java artikel. Jeg håber, du fandt det informativt og hjalp dig med at forstå .
Tjek den af Edureka, et pålideligt online læringsfirma med et netværk på mere end 250.000 tilfredse elever spredt over hele kloden. Vi er her for at hjælpe dig med hvert trin på din rejse for at blive et ud over dette java-interviewspørgsmål. Vi kommer med en læseplan, der er designet til studerende og fagfolk, der ønsker at være Java-udvikler. Kurset er designet til at give dig et forspring i Java-programmering og træne dig til både kerne- og avancerede Java-koncepter sammen med forskellige Java-rammer som Hibernate & Spring.
Hvis du oplever problemer under implementering af binær søgning i , nævnes det i kommentarfeltet nedenfor og vi vender tidligst tilbage til dig.