Hitra metoda za iskanje določenega elementa v razvrščeni matriki je binarno iskanje. Začetna naloga tega algoritma je primerjava ciljne vrednosti s srednjim elementom matrike. Iskanje se šteje za uspešno, če je ciljna vrednost v srednjem elementu. Algoritem bo pogledal v levo polovico matrike, če je ciljna vrednost manjša od sredinskega elementa. Program bo skeniral desno polovico matrike, če je ciljna vrednost večja od sredinskega elementa. Ta metoda se ponavlja, dokler se ciljna vrednost ali obseg iskanja ne izčrpata.
Uporaba:
Podatkovne baze, iskalniki in obdelava podatkov je le nekaj aplikacij, ki uporabljajo strategijo binarnega iskanja.
markdown podčrtaj
Značilnosti:
- Niz vhodnih vrednosti mora biti razvrščen.
- Z vsako ponovitvijo metoda skrči obseg iskanja za polovico, zaradi česar je še posebej učinkovita za ogromne nabore podatkov.
- Algoritem ima O (log n) najslabše časovne kompleksnosti.
- Iskanje želene vrednosti opravi program s strategijo deli in vladaj.
Tukaj je preprost primer algoritma binarnega iskanja, napisanega v C:
#include int binary_search(int arr[], int left, int right, int target) { while (left <= right) { int mid="left" + (right - left) 2; if (arr[mid]="=" target) return mid; } else < left="mid" 1; right="mid" -1; target not found main() arr[]="{1," 3, 5, 7, 9}; n="sizeof(arr)" sizeof(arr[0]); index="binary_search(arr," 0, 1, target); (index="=" -1) printf('target found
'); at %d
', index); 0; pre> <p> <strong>Output:</strong> </p> <pre> Target found at index 2 </pre> <ul> <li>The binary_search function accepts four arguments: the array to search, the left and right search range boundaries, and the target value to look for. The function returns its index if the desired value can be found; else, it returns -1.</li> <li>The main function creates an array arr and a value target. The binary_search function is then used to search the array for the desired value. The function returns the index where the target value was located if it was, the function returns the index at which it was found. Otherwise, the message 'Target not found' is displayed.</li> <li>The binary search algorithm's implementation is basic. We begin by setting the left border to the array's initial index and the right boundary to the array's last index. Once the left boundary is less than or equal to the right border, the array is looped through one more time. We use the formula (left + right) / 2 within the loop to calculate the middle index of the search range. This formula computes the integer value of the middle index's floor.</li> <li>The centre member of the array is contrasted with the target value. We return the index of the middle element if they are equal. We change the right boundary to be one less than the middle index if the desired value is less than the middle element. If not, we adjust the left border so that it is one more than the centre index. We continue doing this until the goal value is obtained or the search space is filled.</li> <li>The temporal complexity of the binary search algorithm, where n is the array size, is O(log n). This is far more efficient than linear search, which has a temporal complexity of O(n), where n is the size of the array.</li> <li>Finally, the binary search technique offers a useful way to locate a particular member in a sorted array. It is easy to build and has an O(log n) time complexity, making it an efficient approach for large datasets.</li> </ul> <h3>Advantages:</h3> <ul> <li>For large datasets, the binary search algorithm is exceptionally efficient, and it is capable of handling a wide range of input sizes.</li> <li>The algorithm is simple to implement in almost all programming languages.</li> </ul> <h3>Disadvantages:</h3> <ul> <li>Before using the binary search technique, the input array must be sorted, which takes more time and memory.</li> <li>The algorithm cannot be applied to unsorted arrays.</li> <li>The algorithm may yield inaccurate results if the input array is not sorted.</li> <li>The binary search algorithm is not appropriate for tiny datasets since the technique's overhead may outweigh its benefits.</li> </ul> <h2>Conclusion:</h2> <p>A sorted array can be quickly searched for a specific element using the binary search technique. It employs a divide-and-conquer strategy to cut the search range in half with each iteration, allowing it to be highly efficient for large datasets. However, before using the binary search technique, the input array must be sorted, which takes extra time and memory. The binary search algorithm is a sophisticated data processing tool that is widely utilised in various sectors.</p> <hr></=> - Funkcija binary_search sprejema štiri argumente: matriko za iskanje, levo in desno mejo obsega iskanja ter ciljno vrednost za iskanje. Funkcija vrne svoj indeks, če je mogoče najti želeno vrednost; sicer vrne -1.
- Glavna funkcija ustvari matriko arr in ciljno vrednost. Funkcija binary_search se nato uporabi za iskanje želene vrednosti v matriki. Funkcija vrne indeks, kjer je bila ciljna vrednost, če je bila, funkcija vrne indeks, na katerem je bila najdena. V nasprotnem primeru se prikaže sporočilo 'Target not found'.
- Izvedba algoritma binarnega iskanja je osnovna. Začnemo z nastavitvijo leve meje na začetni indeks matrike in desne meje na zadnji indeks matrike. Ko je leva meja manjša ali enaka desni meji, se matrika še enkrat premakne skozi zanko. Za izračun srednjega indeksa obsega iskanja uporabljamo formulo (levo + desno) / 2 znotraj zanke. Ta formula izračuna celoštevilsko vrednost dna srednjega indeksa.
- Sredinski član matrike je v nasprotju s ciljno vrednostjo. Vrnemo indeks srednjega elementa, če sta enaka. Desno mejo spremenimo tako, da bo ena manjša od srednjega indeksa, če je želena vrednost manjša od srednjega elementa. Če ni, levo obrobo prilagodimo tako, da je ena večja od sredinskega kazala. To nadaljujemo, dokler ne dosežemo ciljne vrednosti ali dokler ne zapolnimo iskalnega prostora.
- Časovna kompleksnost algoritma binarnega iskanja, kjer je n velikost niza, je O(log n). To je veliko bolj učinkovito kot linearno iskanje, ki ima časovno kompleksnost O(n), kjer je n velikost niza.
- Končno tehnika binarnega iskanja ponuja uporaben način za iskanje določenega člana v razvrščenem nizu. Enostavno ga je zgraditi in ima O(log n) časovno zapletenost, zaradi česar je učinkovit pristop za velike nabore podatkov.
Prednosti:
- Za velike nabore podatkov je algoritem binarnega iskanja izjemno učinkovit in je zmožen obravnavati širok razpon velikosti vhodnih podatkov.
- Algoritem je enostaven za implementacijo v skoraj vseh programskih jezikih.
Slabosti:
- Pred uporabo tehnike binarnega iskanja je treba vhodno polje razvrstiti, kar zahteva več časa in pomnilnika.
- Algoritma ni mogoče uporabiti za nerazvrščene nize.
- Algoritem lahko daje netočne rezultate, če vhodna matrika ni razvrščena.
- Algoritem binarnega iskanja ni primeren za majhne nabore podatkov, saj lahko režijski stroški tehnike odtehtajo njene prednosti.
Zaključek:
V razvrščeni matriki je mogoče hitro poiskati določen element s tehniko binarnega iskanja. Uporablja strategijo deli in vladaj, da z vsako ponovitvijo prepolovi obseg iskanja, kar mu omogoča, da je zelo učinkovit za velike nabore podatkov. Pred uporabo tehnike binarnega iskanja pa je treba vhodno polje razvrstiti, kar zahteva dodaten čas in pomnilnik. Algoritem binarnega iskanja je sofisticirano orodje za obdelavo podatkov, ki se široko uporablja v različnih sektorjih.