En aquest article, parlarem de l'algoritme de cerca binària. La cerca és el procés de trobar algun element concret a la llista. Si l'element està present a la llista, el procés s'anomena reeixit i el procés retorna la ubicació d'aquest element. En cas contrari, es diu que la cerca no ha tingut èxit.
La cerca lineal i la cerca binària són les dues tècniques de cerca populars. Aquí parlarem de l'algoritme de cerca binària.
La cerca binària és la tècnica de cerca que funciona de manera eficient en llistes ordenades. Per tant, per cercar un element en alguna llista mitjançant la tècnica de cerca binària, ens hem d'assegurar que la llista estigui ordenada.
La cerca binària segueix l'enfocament de dividir i guanyar en què la llista es divideix en dues meitats i l'element es compara amb l'element central de la llista. Si es troba la coincidència, es retorna la ubicació de l'element central. En cas contrari, cerquem qualsevol de les meitats en funció del resultat produït a través del partit.
NOTA: La cerca binària es pot implementar en elements de matriu ordenats. Si els elements de la llista no estan ordenats, primer els hem d'ordenar.
Ara, vegem l'algorisme de la cerca binària.
Algorisme
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
Funcionament de la cerca binària
Ara, vegem el funcionament de l'algoritme de cerca binari.
Per entendre el funcionament de l'algorisme de cerca binari, prenem una matriu ordenada. Serà fàcil entendre el funcionament de la cerca binària amb un exemple.
Hi ha dos mètodes per implementar l'algorisme de cerca binària:
- Mètode iteratiu
- Mètode recursiu
El mètode recursiu de cerca binària segueix l'enfocament de dividir i conquerir.
Siguin els elements de la matriu -
Deixeu que l'element a cercar sigui, K = 56
Hem d'utilitzar la fórmula següent per calcular mig de la matriu -
mid = (beg + end)/2
Per tant, a la matriu donada -
suplicar = 0
final = 8
mig = (0 + 8)/2 = 4. Per tant, 4 és la meitat de la matriu.
Ara, s'ha trobat l'element a cercar. Per tant, l'algorisme retornarà l'índex de l'element coincident.
Complexitat de la cerca binària
Ara, vegem la complexitat temporal de la cerca binària en el millor dels casos, el cas mitjà i el pitjor dels casos. També veurem la complexitat espacial de la cerca binària.
1. Complexitat temporal
| Caixa | Complexitat temporal |
|---|---|
| Millor cas | O(1) |
| Cas mitjà | O (inici de sessió) |
| Pitjor dels casos | O (inici de sessió) |
2. Complexitat espacial
| Complexitat espacial | O(1) |
- La complexitat espacial de la cerca binària és O(1).
Implementació de la cerca binària
Ara, anem a veure els programes de cerca binària en diferents llenguatges de programació.
Programa: Escriu un programa per implementar la cerca binària en llenguatge 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)> Sortida
Per tant, això és tot sobre l'article. Espero que l'article us sigui útil i informatiu.