Šiame straipsnyje aptarsime dvejetainės paieškos algoritmą. Paieška yra tam tikro sąrašo elemento suradimo procesas. Jei elementas yra sąraše, procesas vadinamas sėkmingu, o procesas grąžina to elemento vietą. Priešingu atveju paieška vadinama nesėkminga.
Linijinė paieška ir dvejetainė paieška yra du populiarūs paieškos būdai. Čia aptarsime dvejetainės paieškos algoritmą.
Dvejetainė paieška yra paieškos technika, kuri efektyviai veikia surūšiuotuose sąrašuose. Taigi, norėdami ieškoti elemento kokiame nors sąraše naudodami dvejetainę paieškos techniką, turime užtikrinti, kad sąrašas būtų surūšiuotas.
Dvejetainė paieška atliekama pagal „skaldyk ir valdyk“ metodą, kai sąrašas yra padalintas į dvi dalis, o elementas lyginamas su viduriniu sąrašo elementu. Jei atitikmuo randamas, grąžinama vidurinio elemento vieta. Kitu atveju ieškome bet kurioje iš kėlinių, priklausomai nuo rungtynių rezultato.
kaip konvertuoti eilutę į int java
PASTABA: Dvejetainę paiešką galima įgyvendinti surūšiuotuose masyvo elementuose. Jei sąrašo elementai nėra surūšiuoti, pirmiausia turime juos surūšiuoti.
Dabar pažiūrėkime į dvejetainės paieškos algoritmą.
Algoritmas
Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search Step 1: set beg = lower_bound, end = upper_bound, pos = - 1 Step 2: repeat steps 3 and 4 while beg val set end = mid - 1 else set beg = mid + 1 [end of if] [end of loop] Step 5: if pos = -1 print 'value is not present in the array' [end of if] Step 6: exit
Dvejetainės paieškos darbas
Dabar pažiūrėkime, kaip veikia dvejetainis paieškos algoritmas.
Norėdami suprasti dvejetainės paieškos algoritmo veikimą, paimkime surūšiuotą masyvą. Su pavyzdžiu bus lengva suprasti dvejetainės paieškos veikimą.
Yra du dvejetainio paieškos algoritmo įgyvendinimo būdai -
- Iteracinis metodas
- Rekursyvinis metodas
Rekursyvus dvejetainės paieškos metodas vadovaujasi „skaldyk ir valdyk“ principu.
klasė vs objektas java
Tegul masyvo elementai yra -
Tegul ieškomas elementas yra K = 56
Norėdami apskaičiuoti, turime naudoti toliau pateiktą formulę vidurio iš masyvo -
mid = (beg + end)/2
Taigi pateiktame masyve -
elgetauti = 0
galas = 8
kaip sugalvojo mokyklą
vidurio = (0 + 8)/2 = 4. Taigi, 4 yra masyvo vidurys.
Dabar ieškomas elementas rastas. Taigi algoritmas grąžins atitikusio elemento indeksą.
Dvejetainės paieškos sudėtingumas
Dabar pažiūrėkime, koks yra dvejetainės paieškos sudėtingumas geriausiu, vidutiniu ir blogiausiu atveju. Taip pat pamatysime dvejetainės paieškos erdvės sudėtingumą.
1. Laiko sudėtingumas
| Byla | Laiko sudėtingumas |
|---|---|
| Geriausias atvejis | O(1) |
| Vidutinis atvejis | O (prisijungti) |
| Blogiausiu atveju | O (prisijungti) |
2. Erdvės sudėtingumas
| Erdvės sudėtingumas | O(1) |
- Dvejetainės paieškos erdvės sudėtingumas yra O(1).
Dvejetainės paieškos diegimas
Dabar pažiūrėkime dvejetainės paieškos programas skirtingomis programavimo kalbomis.
Programa: Parašykite programą, kuri įgyvendintų dvejetainę paiešką C kalba.
unix vs windows
#include int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{11," 14, 25, 30, 40, 41, 52, 57, 70}; given array val="40;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result printf('the elements are - '); for (int i="0;" < n; i++) printf('%d ', a[i]); printf('
element %d', (res="=" -1) not present array'); at %d position array', res); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-5.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C++.</p> <pre> #include using namespace std; int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{10," 12, 24, 29, 39, 40, 51, 56, 70}; given array val="51;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result cout<<'the elements are - '; for (int i="0;" < n; i++) cout< <a[i]<<' cout<<'
element '<<val; (res="=" -1) not present array'; at '<<res<<' position 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-6.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C#.</p> <pre> using System; class BinarySearch { static int binarySearch(int[] a, int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; static void main() int[] a="{9," 11, 23, 28, 38, 45, 50, 56, 70}; given array int val="70;" value n="a.Length;" size of res="binarySearch(a," 0, n-1, store result console.write('the elements are - '); for (int i="0;" < n; i++) console.write(a[i] + ' console.writeline(); console.writeline('element (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-7.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in Java.</p> <pre> class BinarySearch { static int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; public static void main(string args[]) int a[]="{8," 10, 22, 27, 37, 44, 49, 55, 69}; given array val="37;" value n="a.length;" size of res="binarySearch(a," 0, n-1, store result system.out.print('the elements are: '); for (int i="0;" < n; i++) system.out.print(a[i] + ' system.out.println(); system.out.println('element is: (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-8.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in PHP.</p> <pre> = $beg) { $mid = floor(($beg + $end)/2); if($a[$mid] == $val) { return $mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if($a[$mid] <$val) { return binarysearch($a, $mid+1, $end, $val); } * if the item to be searched is greater than middle, then it can only in right subarray else $beg, $mid-1, -1; $a="array(7," 9, 21, 26, 36, 43, 48, 54, 68); given array $val="68;" value $n="sizeof($a);" size of $res="binarySearch($a," 0, $n-1, store result echo 'the elements are: '; for ($i="0;" $i < $n; $i++) ' , $a[$i]; <br>' , 'Element to be searched is: ' , $val; if ($res == -1) echo ' <br>' , 'Element is not present in the array'; else echo ' <br>' , 'Element is present at ' , $res , ' position of array'; ?> </$val)></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-9.webp" alt="Binary Search Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></val)></pre></val)></pre></val)></pre></val)> Išvestis
Taigi, viskas apie straipsnį. Tikimės, kad straipsnis bus jums naudingas ir informatyvus.