Viens no vissvarīgākajiem datorzinātņu algoritmiem ir binārās meklēšanas algoritms. Bināro meklēšanu var ieviest, izmantojot divas metodes: iteratīvo metodi un rekursīvo metodi. Lai gan abām metodēm ir vienāda laika sarežģītība, iteratīvā metode ir daudz efektīvāka telpas sarežģītības ziņā.
Iteratīvajai metodei ir telpas sarežģītība O(1) salīdzinot ar O(pieteikties) ražots ar rekursīvo metodi. Tātad, kā jūs varat ieviest binārās meklēšanas algoritmu, izmantojot iteratīvo metodi programmās C, C++ un Python?
Kas ir binārā meklēšana?
Binārā meklēšana, kas pazīstama arī kā pusintervāla meklēšana, logaritmiskā meklēšana vai binārā meklēšana, ir algoritms, kas meklē un atgriež elementa pozīciju sakārtotā masīvā. Meklēšanas elements tiek salīdzināts ar vidējo elementu. Ņemot vidējo no apakšējās un augšējās robežas, jūs varat atrast vidējos elementus.
Ja meklēšanas elements ir lielāks par vidējo elementu, tas nozīmē, ka visi elementi kreisajā pusē ir mazāki par meklēšanas elementu. Tātad, vadība pāriet uz masīva labo pusi (ja masīvs ir augošā secībā), palielinot apakšējo robežu līdz nākamā vidējā elementa pozīcijai.
Tāpat, ja meklēšanas elements ir mazāks par vidējo, tas nozīmē, ka visi labajā pusē esošie elementi ir lielāki par meklēšanas elementu. Tātad, vadība pāriet uz masīva kreiso daļu, mainot augšējo robežu uz vidējā elementa iepriekšējo pozīciju.
Tas krasi samazina salīdzinājumu skaitu, salīdzinot ar lineārās meklēšanas ieviešana kur salīdzinājumu skaits ir vienāds ar elementu skaitu sliktākajā gadījumā. Šī metode ir ļoti noderīga, lai atrastu numurus tālruņu grāmatā vai vārdus vārdnīcā.
Šeit ir diagrammas attēlojums Binārās meklēšanas algoritms:
Binārā meklēšana, izmantojot C
Veiciet šīs darbības, lai ieviestu bināro meklēšanu, izmantojot C:
Viss binārās meklēšanas programmas pirmkods, kas izmanto C, C++, Java un Python, ir pieejams šajā GitHub repozitorijs.
Programma definē funkciju, binarySearch(), kas atgriež vai nu atrastās vērtības indeksu, vai -1 ja tas nav klāt:
#iekļauts <stdio.h>
starptbinārā meklēšana(starpt arr[], starpt arr_size, starpt meklēšanas_numurs){
/*... */
}
Funkcija darbojas, iteratīvi sašaurinot meklēšanas vietu. Tā kā binārā meklēšana darbojas uz sakārtotiem masīviem, varat aprēķināt vidu, kam citādi nav jēgas. Varat lūgt lietotājam sakārtotu masīvu vai izmantot kārtošanas algoritmus, piemēram, burbuļu vai atlases kārtošanu.
The zems un augsts mainīgie saglabā indeksus, kas atspoguļo pašreizējās meklēšanas telpas robežas. vidus saglabā indeksu vidū:
starpt zems = 0, augsts = arr_size - 1, vidus;Galvenais kamēr () cilpa sašaurinās meklēšanas vietu. Ja zemā indeksa vērtība kādreiz kļūst lielāka par augsto indeksu, meklēšanas vieta ir izsmelta, tāpēc vērtība nevar būt.
kamēr (zems <= augsts) {
/* turpinās... [1] */
}
atgriezties-1;
Pēc viduspunkta atjaunināšanas cilpas sākumā ir trīs iespējamie rezultāti:
- Ja vērtība viduspunktā ir tā, ko mēs meklējam, atgrieziet šo indeksu.
- Ja viduspunkta vērtība ir lielāka par to, ko mēs meklējam, samaziniet augstāko vērtību.
- Ja viduspunkta vērtība ir mazāka, palieliniet zemo vērtību.
/* [1] ...turpinājums */
vidus = (zems + (augsts - zems)) / 2;
if (arr[mid] == meklēšanas_numurs)
atgriezties vidus;
citsja (arr[mid] > meklēšanas_numurs)
augsts = vidējais - 1;
cits
zems = vidējais + 1;
Pārbaudiet funkciju ar lietotāja ievadi. Izmantot scanf() lai saņemtu ievadi no komandrindas, tostarp masīva lielumu, saturu un meklējamo numuru:
starptgalvenais(){
starpt arr[100], i, arr_size, search_number;
printf("Ievadiet elementu skaitu: ");
scanf("%d", &arr_size);
printf("Lūdzu, ievadiet ciparus: ");par (i = 0; i < arr_size; i++) {
scanf("%d", &arr[i]);
}printf("Ievadiet meklējamo numuru: ");
scanf("%d", &meklēšanas_numurs);i = binārā meklēšana (arr, arr_size, search_number);
ja (i==-1)
printf("Numura nav");
cits
printf("Numurs atrodas pozīcijā %d", i + 1);
atgriezties0;
}
Ja atrodat numuru, parādiet tā pozīciju vai indeksu, pretējā gadījumā tiek parādīts ziņojums, ka numura nav.
Binārā meklēšana, izmantojot C++
Varat konvertēt C programmu par C++ programmu, importējot Ievades izvades straume un izmantot namespace std lai izvairītos no tā atkārtošanas vairākas reizes programmas laikā.
#iekļauts <iostream>
izmantojot nosaukumvietastd;Izmantot cout ar ieguves operatoru << tā vietā printf() un cin ar ievietošanas operatoru >> tā vietā scanf() un jūsu C++ programma ir gatava.
printf("Ievadiet elementu skaitu: ");
cout <<"Ievadiet elementu skaitu: ";
scanf("%d", &arr_size);
cin >> arr_size;Binārā meklēšana, izmantojot Python
Tā kā Python nav iebūvēta atbalsta masīviem, izmantojiet sarakstus. Definējiet funkciju, binarySearch(), kas pieņem trīs parametrus — sarakstu, tā lielumu un meklējamo numuru:
defbinārā meklēšana(arr, arr_size, search_number):
zems = 0
augsts = arr_size - 1
kamēr zems <= augsts:
vidus = zems + (augsts-zems)//2
if arr[mid] == meklēšanas_numurs:
atgriezties vidus
elifs arr[mid] > search_number:
augsts = vidējais - 1
cits:
zems = vidējais + 1
atgriezties-1Inicializējiet divus mainīgos, zems un augsts, lai kalpotu kā saraksta apakšējā un augšējā robeža. Līdzīgi kā C ieviešanā, izmantojiet a kamēr cilpa, kas sašaurina meklēšanas vietu. Palaist vidus lai saglabātu saraksta vidējo vērtību. Python nodrošina grīdas dalīšanas operatoru (//), kas nodrošina lielāko iespējamo veselo skaitli.
Veiciet salīdzinājumus un sašauriniet meklēšanas laukumu, līdz vidējā vērtība ir vienāda ar meklēšanas numuru. Ja meklēšanas numura nav, vadīkla atgriezīsies -1.
arr_size = int (input("Ievadiet elementu skaitu: "))
arr=[]
drukāt ("Lūdzu, ievadiet ciparus: ", beigas="")
i diapazonā (0,arr_size):
arr.append(starpt(ievade()))
search_number = int (input("Ievadiet meklējamo numuru: "))
rezultāts = binārā meklēšana (arr, arr_size, search_number)
ja rezultāts == -1:
drukāt ("Numura nav")
cits:
print ("Numurs ir atrodas pozīcijā ", (rezultāts + 1))Pārbaudiet funkciju ar lietotāja ievadi. Izmantot ievade () lai iegūtu saraksta lielumu, saturu un meklējamo numuru. Izmantot int() lai ierakstītu virknes ievadi, ko Python akceptējis kā noklusējuma vērtību, veselā skaitlī. Lai sarakstam pievienotu ciparus, izmantojiet pievienot () funkciju.
Zvaniet binarySearch() un nodot argumentus. Ja atrodat numuru, parādiet tā pozīciju vai indeksu, pretējā gadījumā tiek parādīts ziņojums, ka numura nav.
Binārās meklēšanas algoritma izvade
Tālāk ir norādīta binārās meklēšanas algoritma izvade, kad elements atrodas masīvā:
Tālāk ir norādīta binārās meklēšanas algoritma izvade, ja elements nav masīvā:
Uzziniet pamata datu struktūras un algoritmus
Meklēšana ir viens no pirmajiem algoritmiem, ko apgūstat, un tas bieži tiek uzdots kodēšanas konkursos, izvietojumos un intervijās. Daži citi algoritmi, kas jums jāapgūst, ir kārtošanas, jaukšanas, dinamiskās programmēšanas, virkņu saskaņošanas un primāruma pārbaudes algoritmi.
Turklāt ir svarīgi saprast algoritmu laika un telpas sarežģītību. Tie ir viens no vissvarīgākajiem datorzinātņu jēdzieniem, lai noteiktu jebkura algoritma efektivitāti. Zinot datu struktūras un algoritmus, jūs noteikti izveidosit labākās programmas.
