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.
Nå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øyForklaring:
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 javaLa 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 2Så 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.