Hva er binært søk i Java? Hvordan implementere det?



Binært søk i Java er en søkealgoritme som finner posisjonen til en målverdi i en sortert matrise. I denne artikkelen vil jeg fortelle deg hvordan du implementerer det ved hjelp av et eksempel.

Søke- og sorteringsalgoritmer er populære algoritmer i alle programmeringsspråk. De er grunnlaget for å forstå det grunnleggende i programmeringen. En slik populær søkealgoritme er Binary Search in . I denne artikkelen vil jeg fortelle deg alt om implementeringen.

Følgende emner er dekket i denne artikkelen:





La oss komme i gang!

Hva er binært søk?

Binær søk i er en søkealgoritme som finner posisjonen til en målverdi i en sortert array . Binært søk sammenligner målverdien med det midtre elementet i matrisen. Denfungerer bare på et sortert sett med elementer. For å bruke binært søk i en samling, må først sorteres.



Binary Search Program in Java - Binary Search in Java - EdurekaNår brukes til å utføre operasjoner på et sortert sett, kan antall iterasjoner alltid reduseres på grunnlag av verdien som det søkes etter. Du kan se i øyeblikksbildet ovenfor for å finne midt element . Analogien med binært søk er å bruke informasjonen som matrisen er sortert og redusere tidskompleksiteten til O (log n) .

Implementering av binær søkealgoritme

La oss ta en titt på pseudokoden nedenfor for å forstå den på en bedre måte.

Prosedyre binary_search A & larr sortert array n & larr størrelse på array x & larr verdi som skal søkes Sett lav = 1 Sett høy = n mens x ikke blir funnet hvis høy

Forklaring:



Trinn 1: Først sammenligner du x med midtelementet.

Steg 2: Hvis x samsvarer med midtelementet, må du returnere midtindeksen.

Trinn 3: Ellers, hvis x er større enn midtelementet, kan x bare ligge i høyre halvparti etter midtelementet. Derfor gjentar du høyre halvdel.

Trinn 4: Ellers, hvis (x er mindre), går du igjen for venstre halvdel.

Slik må du søke etter elementet i den gitte matrisen.

generere en tilfeldig streng java

La oss nå se hvordan du implementerer en binær søkealgoritme rekursivt. Nedenfor viser programmet det samme.

Rekursivt binært søk

offentlig klasse BinarySearch {// Java-implementering av rekursivt binært søk // Returnerer indeks på x hvis den er tilstede i arr [l..h], ellers returnerer -1 int binærsøk (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Hvis elementet er tilstede i selve midten hvis (a [mid] == x) returnerer mid // Hvis element er mindre enn midten, så kan den bare være tilstede i venstre undergruppe hvis (a [midt]> x) returnere binærsøk (arr, l, midt - 1, x) // Ellers kan elementet bare være tilstede i høyre underarrangement retur binær (arr, mid + 1, h, x)} // Vi når hit når elementet ikke er tilstede i array-retur -1} public static void main (String args []) {BinarySearch ob = new BinarySearch () int a [] = {20, 30, 40, 10, 50} int n = a. Lengde int x = 40 int res = ob.binarySearch (a, 0, n - 1, x) hvis (res == -1) System.out .println ('Element ikke tilstede') annet System.out.println ('Element funnet ved indeks' + res)}}

Når du utfører programmet ovenfor, vil det finne elementet som er tilstede i den bestemte indeksen

Element funnet ved indeks 2

Så dette bringer oss til slutten av Binary Search i Java artikkel. Jeg håper du syntes det var informativt og hjalp deg med å forstå .

Sjekk ut av Edureka, et pålitelig online læringsfirma med et nettverk av mer enn 250 000 fornøyde elever spredt over hele verden. Vi er her for å hjelpe deg med hvert trinn på reisen, for å bli et spørsmål i tillegg til dette java-intervjuet. Vi kommer med en læreplan som er designet for studenter og fagpersoner som ønsker å være Java-utvikler. Kurset er designet for å gi deg et forsprang i Java-programmering og trene deg for både kjerne- og avanserte Java-konsepter sammen med forskjellige Java-rammer som Hibernate & Spring.

I tilfelle du får problemer når du implementerer Binary Search i , vennligst nevn det i kommentarfeltet nedenfor og vi vil komme tilbake til deg tidligst.