Vienas iš pagrindinių kompiuterių mokslo algoritmų yra dvejetainės paieškos algoritmas. Dvejetainę paiešką galite įdiegti naudodami du metodus: kartotinį ir rekursinį. Nors abu metodai yra vienodai sudėtingi, iteracinis metodas yra daug efektyvesnis erdvės sudėtingumo požiūriu.

Iteracinis metodas turi erdvės sudėtingumą O(1) lyginant su O (prisijungti) pagamintas rekursiniu metodu. Taigi, kaip galite įdiegti dvejetainės paieškos algoritmą naudodami kartotinį metodą C, C++ ir Python?

Kas yra dvejetainė paieška?

Dvejetainė paieška taip pat žinoma kaip pusinio intervalo paieška, logaritminė paieška arba dvejetainis karpymas yra algoritmas, kuris ieško ir grąžina elemento padėtį surūšiuotame masyve. Paieškos elementas lyginamas su viduriniu elementu. Atsižvelgdami į apatinės ir viršutinės ribos vidurkį, galite rasti vidurinius elementus.

Jei paieškos elementas yra didesnis nei vidurinis, tai reiškia, kad visi elementai kairėje yra mažesni už paieškos elementą. Taigi valdiklis perkeliamas į dešinę masyvo pusę (jei masyvas yra didėjančia tvarka), padidinant apatinę ribą iki kitos vidurinio elemento padėties.

instagram viewer

Panašiai, jei paieškos elementas yra mažesnis už vidurinį elementą, tai reiškia, kad visi elementai dešinėje yra didesni už paieškos elementą. Taigi, valdiklis persikelia į kairę masyvo dalį, pakeitus viršutinę ribą į ankstesnę vidurinio elemento padėtį.

Tai drastiškai sumažina palyginimų skaičių, palyginti su linijinės paieškos įgyvendinimas kur palyginimų skaičius yra lygus elementų skaičiui pagal blogiausią scenarijų. Šis metodas yra labai naudingas ieškant skaičių telefonų knygoje arba žodžius žodyne.

Čia yra diagrama Dvejetainės paieškos algoritmas:

Dvejetainė paieška naudojant C

Atlikite šiuos veiksmus, kad įdiegtumėte dvejetainę paiešką naudodami C:

Visas dvejetainės paieškos programos, naudojant C, C++, Java ir Python, šaltinio kodas yra šioje GitHub saugykla.

Programa apibrėžia funkciją, dvejetainė paieška (), kuris grąžina rastos reikšmės indeksą arba -1 jei jo nėra:

#įtraukti <stdio.h>
tarptdvejetainė paieška(tarpt arr[], tarpt arr_size, tarpt paieškos_numeris){
/*... */
}

Funkcija veikia iteratyviai susiaurindama paieškos erdvę. Kadangi dvejetainė paieška veikia surūšiuotuose masyvuose, galite apskaičiuoti vidurį, kuris kitu atveju nėra prasmingas. Galite paprašyti vartotojo surūšiuoti masyvą arba naudoti rūšiavimo algoritmus, tokius kaip burbulas arba atrankos rūšiavimas.

The žemas ir aukštas kintamieji saugo indeksus, vaizduojančius dabartinės paieškos erdvės ribas. vidurio išsaugo indeksą viduryje:

tarpt žemas = 0, aukštas = arr_size - 1, vidurys;

Pagrindinis kol () kilpa susiaurins paieškos erdvę. Jei žemo indekso reikšmė kada nors tampa didesnė už aukštą, vadinasi, paieškos erdvė išnaudota, todėl reikšmės negali būti.

kol (žemas <= didelis) {
/* tęsiasi... [1] */
 }
grąžinti-1;

Atnaujinus vidurio tašką ciklo pradžioje, yra trys galimi rezultatai:

  1. Jei vidurio taško reikšmė yra ta, kurios ieškome, grąžinkite tą indeksą.
  2. Jei vidurio taško reikšmė yra didesnė už tą, kurios ieškome, sumažinkite didžiausią vertę.
  3. Jei vidurio taško reikšmė mažesnė, padidinkite žemąją. 
/* [1] ...tęsinys */
 vidurys = (žemas + (aukštas - žemas)) / 2;
if (arr[mid] == paieškos_numeris)
grąžinti vidurio;
Kitasjeigu (arr[mid] > paieškos_numeris)
 aukštas = vidutinis - 1;
Kitas
 žemas = vidutinis + 1;

Išbandykite funkciją naudodami vartotojo įvestį. Naudokite scanf() Norėdami gauti įvestį iš komandinės eilutės, įskaitant masyvo dydį, turinį ir skaičių, kurio reikia ieškoti:

tarptpagrindinis(){
tarpt arr[100], i, arr_dydis, paieškos_numeris;
 printf("Įveskite elementų skaičių: ");
 scanf("%d", &arr_size);
 printf("Įveskite skaičius: ");
už (i = 0; i < arr_size; i++) {
 scanf("%d", &arr[i]);
 }


printf("Įveskite numerį, kurio norite ieškoti: ");
 scanf("%d", &paieškos_numeris);


i = dvejetainė paieška (arr, arr_size, search_number);


jei (i==-1)
 printf("Numerio nėra");
Kitas
 printf("Numeris yra %d pozicijoje", i + 1);
grąžinti0;
}

Jei radote numerį, parodykite jo vietą arba rodyklę, priešingu atveju pasirodys pranešimas, kad numerio nėra.

Dvejetainė paieška naudojant C++

Galite konvertuoti C programą į C++ programą importuodami Įvesties išvesties srautas ir naudokite vardų sritį std kad nebūtų kartojama kelis kartus per visą programą.

#įtraukti <iostream>
naudojant vardų erdvėstd;

Naudokite cout su ištraukimo operatoriumi << vietoj printf() ir cin su įterpimo operatoriumi >> vietoj scanf() ir jūsų C++ programa paruošta.

printf("Įveskite elementų skaičių: ");
cout <<"Įveskite elementų skaičių: ";
scanf("%d", &arr_size);
cin >> arr_size;

Dvejetainė paieška naudojant Python

Kadangi Python neturi integruoto masyvų palaikymo, naudokite sąrašus. Apibrėžkite funkciją, dvejetainė paieška (), kuris priima tris parametrus: sąrašą, jo dydį ir skaičių, kurio reikia ieškoti:

defdvejetainė paieška(arr, arr_size, search_number):
 žemas = 0
 aukštas = arr_size – 1
kol žemas <= aukštas:
 vidurys = žemas + (aukštas-žemas)//2
 if arr[mid] == paieškos_numeris:
grąžinti vidurio
elifas arr[mid] > search_number:
 aukštas = vidutinis - 1
Kitas:
 žemas = vidutinis + 1
grąžinti-1

Inicijuoti du kintamuosius, žemas ir aukštas, būti apatinė ir viršutinė sąrašo ribos. Panašiai kaip C įgyvendinimas, naudokite a kol kilpa, kuri susiaurina paieškos erdvę. Inicijuoti vidurio kad išsaugotumėte vidurinę sąrašo reikšmę. Python pateikia grindų padalijimo operatorių (//), kuris pateikia didžiausią įmanomą sveikąjį skaičių.

Atlikite palyginimus ir susiaurinkite paieškos erdvę, kol vidutinė reikšmė bus lygi paieškos skaičiui. Jei paieškos numerio nėra, valdiklis grįš -1.

arr_size = int (input("Įveskite elementų skaičių: "))
arr=[]
spausdinti ("Įveskite skaičius: ", pabaiga ="")
i diapazone (0,arr_size):
 arr.append(tarpt(įvesti ()))
paieškos_numeris = int (input("Įveskite numerį, kurio norite ieškoti: "))
rezultatas = dvejetainė paieška (arr, arr_size, search_number)
jei rezultatas == -1:
 spausdinti ("Numerio nėra")
Kitas:
 print ("Numeris yra yra padėtyje “, (rezultatas + 1))

Išbandykite funkciją naudodami vartotojo įvestį. Naudokite įvestis () Norėdami gauti sąrašo dydį, turinį ir skaičių, kurio reikia ieškoti. Naudokite int() Norėdami įvesti eilutę, kurią Python priėmė kaip numatytąjį, į sveikąjį skaičių. Norėdami įtraukti skaičius į sąrašą, naudokite pridėti () funkcija.

Skambinti dvejetainė paieška () ir perduoti argumentus. Jei radote numerį, parodykite jo vietą arba rodyklę, priešingu atveju pasirodys pranešimas, kad numerio nėra.

Dvejetainės paieškos algoritmo išvestis

Toliau pateikiama dvejetainės paieškos algoritmo išvestis, kai elementas yra masyve:

Toliau pateikiama dvejetainės paieškos algoritmo išvestis, kai elemento nėra masyve:

Sužinokite pagrindines duomenų struktūras ir algoritmus

Paieška yra vienas iš pirmųjų algoritmų, kurį išmokstate, ir dažnai jo prašoma kodavimo konkursuose, vietose ir interviu. Kai kurie kiti algoritmai, kuriuos turėtumėte išmokti, yra rūšiavimo, maišos, dinaminio programavimo, eilučių suderinimo ir pirmumo tikrinimo algoritmai.

Be to, labai svarbu suprasti algoritmų sudėtingumą laike ir erdvėje. Jie yra viena iš svarbiausių kompiuterių mokslo sąvokų nustatant bet kurio algoritmo efektyvumą. Turėdami žinių apie duomenų struktūras ir algoritmus, būtinai sukursite geriausias programas.