În acest articol, vom discuta despre algoritmul de căutare binar. Căutarea este procesul de găsire a unui anumit element din listă. Dacă elementul este prezent în listă, atunci procesul este numit succes și procesul returnează locația acelui element. În caz contrar, căutarea este numită nereușită.
Căutarea liniară și Căutarea binară sunt cele două tehnici de căutare populare. Aici vom discuta despre algoritmul de căutare binar.
Căutarea binară este tehnica de căutare care funcționează eficient pe liste sortate. Prin urmare, pentru a căuta un element într-o listă folosind tehnica de căutare binară, trebuie să ne asigurăm că lista este sortată.
Căutarea binară urmează abordarea împărțiți și cuceriți, în care lista este împărțită în două jumătăți, iar elementul este comparat cu elementul din mijloc al listei. Dacă se găsește potrivirea, se returnează locația elementului din mijloc. În caz contrar, căutăm în oricare dintre jumătăți în funcție de rezultatul produs prin meci.
NOTĂ: Căutarea binară poate fi implementată pe elemente de matrice sortate. Dacă elementele listei nu sunt aranjate într-o manieră sortată, trebuie mai întâi să le sortăm.
Acum, să vedem algoritmul Căutării binare.
Algoritm
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
Funcționarea căutării binare
Acum, să vedem funcționarea algoritmului de căutare binar.
alfabet cu numere
Pentru a înțelege funcționarea algoritmului de căutare binar, să luăm o matrice sortată. Va fi ușor de înțeles funcționarea căutării binare cu un exemplu.
Există două metode de implementare a algoritmului de căutare binar -
- Metoda iterativă
- Metoda recursiva
Metoda recursivă de căutare binară urmează abordarea împărțiți și cuceriți.
Fie elementele matricei sunt -
Elementul de căutat este, K = 56
Trebuie să folosim formula de mai jos pentru a calcula mijlocul a matricei -
mid = (beg + end)/2
Deci, în matricea dată -
implora = 0
Sfârşit = 8
mijlocul = (0 + 8)/2 = 4. Deci, 4 este mijlocul matricei.
Acum, elementul de căutat este găsit. Deci algoritmul va returna indexul elementului potrivit.
Complexitatea căutării binare
Acum, să vedem complexitatea de timp a căutării binare în cel mai bun caz, caz mediu și cel mai rău caz. Vom vedea, de asemenea, complexitatea spațială a căutării binare.
1. Complexitatea timpului
| Caz | Complexitatea timpului |
|---|---|
| Cel mai bun caz | O(1) |
| Caz mediu | O(logn) |
| Cel mai rău caz | O(logn) |
2. Complexitatea spațială
| Complexitatea spațială | O(1) |
- Complexitatea spațială a căutării binare este O(1).
Implementarea Căutării binare
Acum, să vedem programele de căutare Binary în diferite limbaje de programare.
Program: Scrieți un program pentru a implementa căutarea binară în limbaj C.
#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)> Ieșire
Deci, asta e totul despre articol. Sper că articolul vă va fi util și informativ.