Čo je to binárne vyhľadávanie v prostredí Java? Ako to implementovať?



Binárne vyhľadávanie v Jave je vyhľadávací algoritmus, ktorý zisťuje polohu cieľovej hodnoty v zoradenom poli. V tomto článku vám poviem, ako ho implementovať pomocou príkladu.

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:





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ť.



Binárny vyhľadávací program v Jave - Binárne vyhľadávanie v Jave - EdurekaKeď 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 jave

Pozrime 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 2

Tý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.