Šajā rakstā mēs apspriedīsim binārās meklēšanas algoritmu. Meklēšana ir kāda konkrēta elementa atrašana sarakstā. Ja elements ir sarakstā, process tiek saukts par veiksmīgu, un process atgriež šī elementa atrašanās vietu. Pretējā gadījumā meklēšana tiek saukta par neveiksmīgu.
Lineārā meklēšana un binārā meklēšana ir divas populāras meklēšanas metodes. Šeit mēs apspriedīsim binārās meklēšanas algoritmu.
Binārā meklēšana ir meklēšanas paņēmiens, kas efektīvi darbojas sakārtotos sarakstos. Tādējādi, lai meklētu elementu kādā sarakstā, izmantojot bināro meklēšanas paņēmienu, mums ir jānodrošina, ka saraksts ir sakārtots.
Binārā meklēšana seko sadali un iekaro pieejai, kurā saraksts tiek sadalīts divās daļās, un vienums tiek salīdzināts ar saraksta vidējo elementu. Ja atbilstība tiek atrasta, tiek atgriezta vidējā elementa atrašanās vieta. Pretējā gadījumā mēs meklējam kādu no puslaikiem atkarībā no spēles rezultāta.
PIEZĪME. Bināro meklēšanu var ieviest sakārtotos masīva elementos. Ja saraksta elementi nav sakārtoti, vispirms tie ir jāsakārto.
Tagad apskatīsim binārās meklēšanas algoritmu.
Algoritms
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
Binārās meklēšanas darbība
Tagad apskatīsim binārās meklēšanas algoritma darbību.
Lai saprastu binārās meklēšanas algoritma darbību, ņemsim sakārtotu masīvu. Izmantojot piemēru, būs viegli saprast binārās meklēšanas darbību.
Ir divas metodes, kā ieviest bināro meklēšanas algoritmu -
- Iteratīvā metode
- Rekursīvā metode
Binārās meklēšanas rekursīvā metode seko sadali un valdi pieejai.
Lai masīva elementi ir -
Ļaujiet meklētajam elementam, K = 56
Lai aprēķinātu, mums ir jāizmanto tālāk norādītā formula vidus no masīva -
mid = (beg + end)/2
Tātad dotajā masīvā -
ubagot = 0
beigas = 8
vidus = (0 + 8)/2 = 4. Tātad 4 ir masīva vidusdaļa.
Tagad meklējamais elements ir atrasts. Tātad algoritms atgriezīs atbilstošā elementa indeksu.
Binārās meklēšanas sarežģītība
Tagad apskatīsim binārās meklēšanas laika sarežģītību labākajā, vidējā un sliktākajā gadījumā. Mēs redzēsim arī binārās meklēšanas sarežģītību telpā.
1. Laika sarežģītība
| Lieta | Laika sarežģītība |
|---|---|
| Labākais gadījums | O(1) |
| Vidējais gadījums | O(pieteikties) |
| Sliktākajā gadījumā | O(pieteikties) |
2. Telpas sarežģītība
| Kosmosa sarežģītība | O(1) |
- Binārās meklēšanas telpas sarežģītība ir O(1).
Binārās meklēšanas ieviešana
Tagad apskatīsim binārās meklēšanas programmas dažādās programmēšanas valodās.
Programma: Uzrakstiet programmu binārās meklēšanas ieviešanai C valodā.
#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)> Izvade
Tātad, tas viss par rakstu. Cerams, ka raksts jums būs noderīgs un informatīvs.