In questo articolo discuteremo dell'algoritmo di ricerca binaria. La ricerca è il processo di ricerca di un elemento particolare nell'elenco. Se l'elemento è presente nell'elenco, il processo viene considerato riuscito e restituisce la posizione di quell'elemento. In caso contrario, la ricerca viene definita non riuscita.
La ricerca lineare e la ricerca binaria sono le due tecniche di ricerca più diffuse. Qui discuteremo dell'algoritmo di ricerca binaria.
La ricerca binaria è la tecnica di ricerca che funziona in modo efficiente su elenchi ordinati. Pertanto, per cercare un elemento in una lista utilizzando la tecnica di ricerca binaria, dobbiamo assicurarci che la lista sia ordinata.
La ricerca binaria segue l'approccio divide et impera in cui l'elenco è diviso in due metà e l'elemento viene confrontato con l'elemento centrale dell'elenco. Se viene trovata la corrispondenza, viene restituita la posizione dell'elemento centrale. Altrimenti, cercheremo in uno dei due tempi a seconda del risultato prodotto durante la partita.
NOTA: la ricerca binaria può essere implementata su elementi di array ordinati. Se gli elementi della lista non sono disposti in modo ordinato, dobbiamo prima ordinarli.
Ora vediamo l'algoritmo della ricerca binaria.
Algoritmo
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
Funzionamento della ricerca binaria
Ora vediamo il funzionamento dell'algoritmo di ricerca binaria.
Per comprendere il funzionamento dell'algoritmo di ricerca binaria, prendiamo un array ordinato. Sarà facile comprendere il funzionamento della ricerca binaria con un esempio.
alfabeto con numeri
Esistono due metodi per implementare l'algoritmo di ricerca binaria:
- Metodo iterativo
- Metodo ricorsivo
Il metodo ricorsivo della ricerca binaria segue l'approccio divide et impera.
Lascia che gli elementi dell'array siano:
Lascia che l'elemento da cercare sia, K = 56
Dobbiamo utilizzare la formula seguente per calcolare il metà della matrice -
mid = (beg + end)/2
Quindi, nell'array dato -
elemosinare = 0
FINE = 8
metà = (0 + 8)/2 = 4. Quindi, 4 è la metà dell'array.
Ora l'elemento da cercare è trovato. Quindi l'algoritmo restituirà l'indice dell'elemento corrispondente.
Complessità della ricerca binaria
Ora vediamo la complessità temporale della ricerca binaria nel caso migliore, medio e peggiore. Vedremo anche la complessità spaziale della ricerca binaria.
1. Complessità temporale
| Caso | Complessità temporale |
|---|---|
| Caso migliore | O(1) |
| Caso medio | O(log) |
| Caso peggiore | O(log) |
2. Complessità spaziale
| Complessità spaziale | O(1) |
- La complessità spaziale della ricerca binaria è O(1).
Implementazione della ricerca binaria
Vediamo ora i programmi di ricerca binaria nei diversi linguaggi di programmazione.
decodifica javascript base64
Programma: Scrivere un programma per implementare la ricerca binaria in linguaggio 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)> Produzione
Quindi, questo è tutto sull'articolo. Spero che l'articolo ti sia utile e informativo.