TechCodeview

O metodă rapidă de localizare a unui anumit element într-o matrice sortată este o căutare binară. Sarcina inițială a acestui algoritm este de a compara valoarea țintă cu elementul de mijloc al matricei. Căutarea este considerată reușită dacă valoarea țintă este conținută în elementul din mijloc. Algoritmul va căuta în jumătatea stângă a matricei dacă valoarea obiectivului este mai mică decât elementul central. Programul va scana jumătatea dreaptă a matricei dacă valoarea obiectivului este mai mare decât elementul central. Această metodă se repetă până când valoarea obiectivului sau intervalul de căutare este epuizat.

lista c#

Utilizare:

Bazele de date, motoarele de căutare și procesarea datelor sunt doar câteva dintre aplicațiile care folosesc strategia de căutare binară.

Caracteristici:

• Matricea valorilor de intrare trebuie sortată.
• Cu fiecare iterație, metoda micșorează intervalul de căutare la jumătate, făcând-o deosebit de eficientă pentru seturi de date uriașe.
• Algoritmul are o complexitate de timp O (log n) în cel mai rău caz.
• Găsirea valorii dorite se face de către program folosind o strategie divide-and-conquer.

Iată un exemplu simplu de algoritm de căutare binar scris în C:

java indexof

 #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 &apos;Target not found&apos; is displayed.</li> <li>The binary search algorithm&apos;s implementation is basic. We begin by setting the left border to the array&apos;s initial index and the right boundary to the array&apos;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&apos;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&apos;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></=>

• Funcția binary_search acceptă patru argumente: matricea de căutat, limitele intervalului de căutare din stânga și din dreapta și valoarea țintă de căutat. Funcția își returnează indexul dacă poate fi găsită valoarea dorită; altfel, se întoarce -1.
• Funcția principală creează o matrice arr și o valoare țintă. Funcția binary_search este apoi folosită pentru a căuta în matrice valoarea dorită. Funcția returnează indexul la care a fost localizată valoarea țintă dacă a fost, funcția returnează indexul la care a fost găsită. În caz contrar, este afișat mesajul „Target not found”.
• Implementarea algoritmului de căutare binar este de bază. Începem prin a seta marginea din stânga la indexul inițial al matricei și limita din dreapta la ultimul index al matricei. Odată ce granița din stânga este mai mică sau egală cu marginea din dreapta, matricea este recirculată încă o dată. Folosim formula (stânga + dreapta) / 2 în cadrul buclei pentru a calcula indicele mijlociu al intervalului de căutare. Această formulă calculează valoarea întreagă a etajului indexului din mijloc.
• Membrul central al matricei este în contrast cu valoarea țintă. Returnăm indicele elementului din mijloc dacă sunt egali. Schimbăm limita dreaptă pentru a fi cu o mai mică decât indicele din mijloc dacă valoarea dorită este mai mică decât elementul din mijloc. Dacă nu, ajustăm chenarul din stânga astfel încât să fie cu unul mai mult decât indexul din centru. Continuăm să facem acest lucru până când se obține valoarea obiectivului sau se umple spațiul de căutare.
• Complexitatea temporală a algoritmului de căutare binar, unde n este dimensiunea matricei, este O(log n). Aceasta este mult mai eficientă decât căutarea liniară, care are o complexitate temporală de O(n), unde n este dimensiunea matricei.
• În cele din urmă, tehnica de căutare binară oferă o modalitate utilă de a localiza un anumit membru într-o matrice sortată. Este ușor de construit și are o complexitate de timp O(log n), ceea ce o face o abordare eficientă pentru seturi mari de date.

Avantaje:

• Pentru seturi mari de date, algoritmul de căutare binar este excepțional de eficient și este capabil să gestioneze o gamă largă de dimensiuni de intrare.
• Algoritmul este simplu de implementat în aproape toate limbajele de programare.

Dezavantaje:

• Înainte de a utiliza tehnica de căutare binară, matricea de intrare trebuie sortată, ceea ce necesită mai mult timp și memorie.
• Algoritmul nu poate fi aplicat matricelor nesortate.
• Algoritmul poate da rezultate inexacte dacă matricea de intrare nu este sortată.
• Algoritmul de căutare binar nu este adecvat pentru seturile de date mici, deoarece costul general al tehnicii poate depăși beneficiile acesteia.

Concluzie:

O matrice sortată poate fi căutată rapid pentru un anumit element folosind tehnica de căutare binară. Utilizează o strategie de împărțire și cucerire pentru a reduce intervalul de căutare la jumătate cu fiecare iterație, permițându-i să fie foarte eficient pentru seturi de date mari. Cu toate acestea, înainte de a utiliza tehnica de căutare binară, matricea de intrare trebuie sortată, ceea ce necesită timp și memorie suplimentară. Algoritmul de căutare binar este un instrument sofisticat de procesare a datelor care este utilizat pe scară largă în diferite sectoare.