Kas ir binārā meklēšana Java? Kā to īstenot?

Bināra meklēšana Java ir meklēšanas algoritms, kas atrod mērķa vērtības pozīciju sakārtotā masīvā. Šajā rakstā es jums pastāstīšu, kā to īstenot, izmantojot piemēru.

Meklēšanas un šķirošanas algoritmi ir populāri algoritmi jebkurā programmēšanas valodā. Tie ir pamats, lai izprastu programmēšanas pamatus. Viens no šādiem populāriem meklēšanas algoritmiem ir binārā meklēšana . Šajā rakstā es jums visu pastāstīšu par tā ieviešanu.

Šajā rakstā ir apskatītas šādas tēmas:





Sāksim!

Kas ir binārā meklēšana?

Binārā meklēšana ir meklēšanas algoritms, kas atrod mērķa vērtības pozīciju sakārtotā masīvs . Binārā meklēšana salīdzina mērķa vērtību ar masīva vidējo elementu. Tādarbojas tikai ar sakārtotu elementu kopu. Lai kolekcijā izmantotu bināro meklēšanu, vispirms ir jāšķiro.



Binārā meklēšanas programma Java valodā - Bināra meklēšana Java valodā - EdurekaKad tiek izmantots, lai veiktu darbības ar sakārtotu kopu, atkārtojumu skaitu vienmēr var samazināt, pamatojoties uz meklējamo vērtību. Iepriekš redzamajā momentuzņēmumā varat redzēt vidus elements . Binārās meklēšanas analoģija ir izmantot masīva sakārtoto informāciju un samazināt laika sarežģītību O (log n) .

Binārās meklēšanas algoritma ieviešana

Apskatīsim zemāk esošo pseidokodu, lai to labāk izprastu.

Procedūra binary_search & & larr sakārtots masīvs n & larr masīva izmērs x & larr meklējamā vērtība Set low = 1 Iestatiet high = n, kamēr x nav atrasts, ja augsts

Paskaidrojums:



1. darbība: Vispirms salīdziniet x ar vidējo elementu.

2. darbība: Ja x sakrīt ar vidējo elementu, jums jāatgriež vidējais indekss.

3. solis: Citādi, ja x ir lielāks par vidējo elementu, tad x var gulēt tikai labās puses pusmasīvā pēc vidējā elementa. Tādējādi jūs atkārtojat pareizo pusi.

4. solis: Citādi, ja (x ir mazāks), tad atkārtojas kreisajai pusei.

Tā jums ir jāmeklē elements attiecīgajā masīvā.

mācīties ssis soli pa solim

Apskatīsim, kā rekursīvi ieviest binārā meklēšanas algoritmu. Zemāk redzamā programma parāda to pašu.

Rekursīvā binārā meklēšana

public class BinarySearch {// rekursīvās binārās meklēšanas Java ieviešana // Atgriež x indeksu, ja tas ir arr [l..h], citādi atgriež -1 int bināro meklēšanu (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Ja elements atrodas pašā vidū, ja (a [mid] == x) atgriežas vidū // If elements ir mazāks par vidu, tad kreisajā apakšdarījumā tas var būt tikai tad, ja (a [mid]> x) atgriež bināro meklēšanu (arr, l, vidū - 1, x) // Cits elements var būt tikai labajā apakšzonā (arr, mid + 1, h, x)} // Mēs nonākam šeit, kad elements nav masīvā return -1} public static void main (String args []) {BinarySearch ob = new BinarySearch () int a [] = {20, 30, 40, 10, 50} int n = a. Garums int x = 40 int res = ob.binārā meklēšana (a, 0, n - 1, x) if (res == -1) System.out .println ('Element nav') else System.out.println ('Elements atrasts indeksā' + res)}}

Izpildot iepriekš minēto programmu, tas atradīs elementu, kas atrodas konkrētajā indeksā

Elements atrasts 2. indeksā

Tātad tas mūs noved pie binārā meklēšanas beigām Java rakstu. Es ceru, ka jūs to uzskatījāt par informatīvu un palīdzējāt saprast .

Pārbaudiet Autors: Edureka, uzticams tiešsaistes mācību uzņēmums ar vairāk nekā 250 000 apmierinātu izglītojamo tīklu visā pasaulē. Mēs esam šeit, lai palīdzētu jums katrā solī jūsu ceļojumā, lai kļūtu par papildus šiem java intervijas jautājumiem. Mēs izdomājam mācību programmu, kas paredzēta studentiem un profesionāļiem, kuri vēlas būt Java izstrādātāji. Kurss ir paredzēts, lai dotu jums iespēju sākt Java programmēšanu un apmācīt gan Java, gan uzlabotas koncepcijas, kā arī dažādas Java struktūras, piemēram, Hibernate & Spring.

Gadījumā, ja, īstenojot bināro meklēšanu, rodas kādas grūtības, , lūdzu, pieminējiet to komentāru sadaļā zemāk un mēs ar jums sazināsimies ātrāk.