En snabb metod för att lokalisera ett visst element i en sorterad array är en binär sökning. Den första uppgiften för denna algoritm är att jämföra målvärdet med arrayens mittelement. Sökningen anses lyckad om målvärdet finns i mittelementet. Algoritmen kommer att titta i den vänstra halvan av arrayen om målvärdet är mindre än mittelementet. Programmet kommer att skanna den högra halvan av arrayen om målvärdet är större än mittelementet. Denna metod upprepas tills antingen målvärdet eller sökintervallet är slut.
Användande:
Databaser, sökmotorer och databehandling är bara några av de applikationer som använder den binära sökstrategin.
Egenskaper:
- Matrisen av indatavärden måste sorteras.
- Med varje iteration minskar metoden sökintervallet med hälften, vilket gör den särskilt effektiv för stora datamängder.
- Algoritmen har en O (log n) värsta tänkbara tidskomplexitet.
- Att hitta det önskade värdet görs av programmet som använder en dela-och-härska-strategi.
Här är ett enkelt exempel på den binära sökalgoritmen skriven i 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></=> - Funktionen binary_search accepterar fyra argument: arrayen att söka, vänster och höger sökintervallsgränser och målvärdet att leta efter. Funktionen returnerar sitt index om det önskade värdet kan hittas; annars returnerar den -1.
- Huvudfunktionen skapar en array arr och ett värdemål. Funktionen binary_search används sedan för att söka i arrayen efter det önskade värdet. Funktionen returnerar indexet där målvärdet fanns om det fanns, funktionen returnerar indexet där det hittades. Annars visas meddelandet 'Målet hittades inte'.
- Implementeringen av den binära sökalgoritmen är grundläggande. Vi börjar med att sätta den vänstra gränsen till arrayens initiala index och den högra gränsen till arrayens sista index. När den vänstra gränsen är mindre än eller lika med den högra gränsen, går arrayen igenom en gång till. Vi använder formeln (vänster + höger) / 2 inom slingan för att beräkna mittindexet för sökintervallet. Denna formel beräknar heltalsvärdet för mittindexets golv.
- Mittelementet i arrayen kontrasteras med målvärdet. Vi returnerar indexet för mittelementet om de är lika. Vi ändrar den högra gränsen till att vara en mindre än mittindexet om det önskade värdet är mindre än mittelementet. Om inte, justerar vi den vänstra kanten så att den är en mer än mittindexet. Vi fortsätter att göra detta tills målvärdet erhålls eller sökutrymmet är fyllt.
- Den tidsmässiga komplexiteten för den binära sökalgoritmen, där n är arraystorleken, är O(log n). Detta är mycket mer effektivt än linjär sökning, som har en tidsmässig komplexitet av O(n), där n är storleken på arrayen.
- Slutligen erbjuder den binära söktekniken ett användbart sätt att lokalisera en viss medlem i en sorterad array. Det är lätt att bygga och har en O(log n) tidskomplexitet, vilket gör det till ett effektivt tillvägagångssätt för stora datamängder.
Fördelar:
- För stora datamängder är den binära sökalgoritmen exceptionellt effektiv och den kan hantera ett brett spektrum av indatastorlekar.
- Algoritmen är enkel att implementera i nästan alla programmeringsspråk.
Nackdelar:
- Innan du använder den binära söktekniken måste inmatningsmatrisen sorteras, vilket tar mer tid och minne.
- Algoritmen kan inte tillämpas på osorterade arrayer.
- Algoritmen kan ge felaktiga resultat om inmatningsmatrisen inte sorteras.
- Den binära sökalgoritmen är inte lämplig för små datamängder eftersom teknikens omkostnader kan uppväga dess fördelar.
Slutsats:
En sorterad array kan snabbt sökas efter ett specifikt element med den binära söktekniken. Den använder en dela-och-härska-strategi för att halvera sökintervallet med varje iteration, vilket gör att det är mycket effektivt för stora datamängder. Men innan du använder den binära söktekniken måste inmatningsmatrisen sorteras, vilket tar extra tid och minne. Den binära sökalgoritmen är ett sofistikerat databearbetningsverktyg som används allmänt inom olika sektorer.