Haku- ja lajittelualgoritmit ovat suosittuja algoritmeja millä tahansa ohjelmointikielellä. Ne ovat perusta ohjelmoinnin perusteiden ymmärtämiselle. Yksi tällainen suosittu hakualgoritmi on Binary Search in . Tässä artikkelissa kerron teille kaikille sen toteuttamisesta.
Tässä artikkelissa käsitellään seuraavia aiheita:
Aloitetaan!
Mikä on binaarihaku?
Binaarihaku on hakualgoritmi, joka löytää kohdearvon sijainnin lajitellussa taulukko . Binaarihaku vertaa kohde-arvoa matriisin keskiosaan. Setoimii vain lajiteltujen elementtien joukossa. Jos haluat käyttää binäärihakua kokoelmassa, on ensin lajiteltava.
Kun käytetään suorittamaan toimintoja lajitellulle joukolle, iteraatioiden määrää voidaan aina vähentää etsittävän arvon perusteella. Näet yllä olevasta tilannekuvasta keskiosa . Binaarihaun analogia on käyttää tietoja, jotka taulukko on lajiteltu ja vähentää ajan monimutkaisuus O (log n) .
Binaarihakualgoritmin toteuttaminen
Katsotaanpa alla olevaa näennäiskoodia ymmärtämään sitä paremmin.
Menettely binary_search A & larr-lajiteltu taulukko n & larr-taulukon koko x & larr-arvo etsittäväksi Aseta matala = 1 Aseta korkea = n, kun x ei löydy, jos korkeaSelitys:
Vaihe 1: Vertaa ensin x: ää keskielementtiin.
Vaihe 2: Jos x vastaa keskielementtiä, sinun on palautettava keskihakemisto.
Vaihe 3: Muuten, jos x on suurempi kuin keskielementti, niin x voi olla vain oikean puolen puolimatriisissa keskielementin jälkeen. Siksi toistat oikean puoliskon.
Vaihe 4: Muuten, jos (x on pienempi), toistu sitten vasemmalle puoliskolle.
Näin sinun täytyy etsiä elementtiä annetusta taulukosta.
pl sql -opetusohjelma, jossa on esimerkkejäKatsotaan nyt, kuinka binäärinen hakualgoritmi otetaan käyttöön rekursiivisesti. Alla oleva ohjelma osoittaa saman.
Rekursiivinen binäärihaku
public class BinarySearch {// rekursiivisen binäärihaun Java-toteutus // Palauttaa x: n indeksin, jos se on taulukossa arr [l..h], muuten palauttaa -1 int binarySearch (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Jos elementti on itse keskellä, jos (a [mid] == x) palaa keskelle // If elementti on pienempi kuin puolivälissä, se voi olla läsnä vasemmassa osapiirissä vain, jos (a [keski]> x) palaa binaarihakuun (arr, l, puolivälissä - 1, x) // Muut elementti voi olla läsnä vain oikeanpuoleisessa alikuvassa (arr, mid + 1, h, x)} // Saavumme tänne, kun elementtiä ei ole taulukossa return -1} public static void main (String args []) {BinarySearch ob = new BinarySearch () int a [] = {20, 30, 40, 10, 50} int n = a. Pituus int x = 40 int res = ob.binarySearch (a, 0, n - 1, x) if (res == -1) System.out .println ('Elementtiä ei ole') else System.out.println ('Elementti löytyy hakemistosta' + res)}}Suoritettaessa yllä olevaa ohjelmaa se etsii tietyssä hakemistossa olevan elementin
Elementti löytyy hakemistosta 2Joten tämä vie meidät binäärihaun loppuun Java artikla. Toivon, että pidit siitä informatiivisena ja autoit ymmärtämisessä .
Katso Edureka, luotettava verkko-oppimisyritys, jolla on yli 250 000 tyytyväisen oppijan verkosto, joka levisi ympäri maailmaa. Olemme täällä auttaaksemme sinua kaikissa vaiheissasi matkallasi, siitä, että tulemme tämän java-haastattelukysymyksen lisäksi. Olemme keksineet opetussuunnitelman, joka on tarkoitettu opiskelijoille ja ammattilaisille, jotka haluavat olla Java-kehittäjiä. Kurssi on suunniteltu antamaan sinulle etumatka Java-ohjelmointiin ja kouluttamaan sekä ydin- että edistyneitä Java-konsepteja sekä erilaisia Java-kehyksiä, kuten Hibernate & Spring.
Jos sinulla on vaikeuksia binäärihaun toteuttamisessa , mainitse se alla olevassa kommenttiosassa ja palaamme sinulle aikaisintaan.