Algoritmy vyhľadávania a triedenia sú populárne algoritmy vo všetkých programovacích jazykoch. Sú základom pre pochopenie základov programovania. Jeden taký populárny vyhľadávací algoritmus je Binárne vyhľadávanie v . V tomto článku vám poviem všetko o jeho implementácii.
V tomto článku sa venujeme týmto témam:
- Čo je to binárne vyhľadávanie?
- Implementácia algoritmu binárneho vyhľadávania
- Rekurzívne binárne vyhľadávanie
Začnime!
Čo je to binárne vyhľadávanie?
Binárne vyhľadávanie v je a vyhľadávací algoritmus, ktorý nájde polohu cieľovej hodnoty v triedenom pole . Binárne vyhľadávanie porovnáva cieľovú hodnotu so stredným prvkom poľa. Tofunguje iba na triedenej množine prvkov. Ak chcete v zbierke použiť binárne vyhľadávanie, najskôr treba roztriediť.
Keď sa používa na vykonávanie operácií na triedenej množine, počet iterácií sa dá vždy znížiť na základe hodnoty, ktorá sa prehľadáva. Na horeuvedenej snímke hľadania stredný prvok . Analogiou binárneho vyhľadávania je použitie informácií, ktoré sú zoradené v poli, a zníženie časovej zložitosti na O (log n) .
Implementácia algoritmu binárneho vyhľadávania
Pozrime sa na nasledujúci pseudokód, aby sme ho lepšie pochopili.
Procedúra binary_search A & larr zoradené pole n & larr veľkosť poľa x & larr hodnota, ktorá sa má prehľadať Nastaviť nízko = 1 Nastaviť vysoko = n zatiaľ čo x sa nenájde, ak je vysokéVysvetlenie:
Krok 1: Najskôr porovnajte x so stredným prvkom.
Krok 2: Ak sa x zhoduje so stredným prvkom, musíte vrátiť stredný index.
Krok 3: Inak, ak je x väčšie ako stredný prvok, potom x môže ležať iba v polovičnom poli na pravej strane za stredným prvkom. Preto opakujete pravú polovicu.
Krok 4: Inak, ak (x je menšie), potom sa opakujte pre ľavú polovicu.
Takto musíte vyhľadať prvok v danom poli.
ako vyhľadať znak v javePozrime sa teraz, ako implementovať algoritmus binárneho vyhľadávania rekurzívne. Nižšie uvedený program ukazuje to isté.
Rekurzívne binárne vyhľadávanie
verejná trieda BinarySearch {// Implementácia Javy rekurzívneho binárneho vyhľadávania // Vráti index x, ak je prítomný v arr [l..h], inak vráti -1 int binarySearch (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Ak je prvok prítomný v samom strede if (a [mid] == x) vráti stred // If element je menší ako stred, potom môže byť prítomný iba v ľavom podskupine, ak (a [stred]> x) vráti binarySearch (arr, l, mid - 1, x) // Else the element can only be only in right subarray return binarySearch (arr, mid + 1, h, x)} // Dostaneme sa sem, keď prvok nie je prítomný v poli return -1} public static void main (String args []) {BinarySearch ob = new BinarySearch () int a [] = {20, 30, 40, 10, 50} int n = a.length int x = 40 int res = ob.binarySearch (a, 0, n - 1, x) if (res == -1) System.out .println ('Element not present') else System.out.println ('Element found at index' + res)}}Pri vykonávaní vyššie uvedeného programu vyhľadá prvok prítomný v konkrétnom indexe
Prvok nájdený v indexe 2Týmto sa dostávame na koniec Binárneho vyhľadávania v Java článok. Dúfam, že ste to našli poučné a pomohli vám pochopiť .
Pozrite sa na autor: Edureka, dôveryhodná online vzdelávacia spoločnosť so sieťou viac ako 250 000 spokojných študentov rozmiestnených po celom svete. Sme tu, aby sme vám pomohli s každým krokom na vašej ceste, aby sme sa nestali popri otázkach týkajúcich sa tohto java rozhovoru. Vymyslíme učebné osnovy určené pre študentov a profesionálov, ktorí sa chcú stať vývojármi Java. Kurz je navrhnutý tak, aby vám dal náskok v programovaní v jazyku Java a naučil vás základné aj pokročilé koncepty jazyka Java spolu s rôznymi rámcami Java, ako je Hibernate & Spring.
V prípade, že sa pri implementácii Binárneho vyhľadávania vo Windows vyskytnú nejaké ťažkosti , uveďte to v sekcii komentárov nižšie a ozveme sa vám najskôr.