A bináris keresés egy gyors módszer egy adott elem megkeresésére egy rendezett tömbben. Ennek az algoritmusnak a kezdeti feladata a célérték összehasonlítása a tömb középső elemével. A keresés akkor tekinthető sikeresnek, ha a célérték a középső elemben található. Az algoritmus a tömb bal felében fog keresni, ha a célérték kisebb, mint a középső elem. A program a tömb jobb felét vizsgálja, ha a célérték nagyobb, mint a középső elem. Ezt a módszert addig ismételjük, amíg a célérték vagy a keresési tartomány ki nem merül.
Használat:
Az adatbázisok, a keresőmotorok és az adatfeldolgozás csak néhány a bináris keresési stratégiát használó alkalmazások közül.
Jellemzők:
- A bemeneti értékek tömbjét rendezni kell.
- A módszer minden iterációval felére csökkenti a keresési tartományt, így különösen hatékony nagy adathalmazok esetén.
- Az algoritmusnak van egy O (log n) legrosszabb eseti összetettsége.
- A kívánt érték megtalálását a program oszd meg és uralkodj stratégiával végzi el.
Íme egy egyszerű példa a C-ben írt bináris keresési algoritmusra:
#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></=> - A binary_search függvény négy argumentumot fogad el: a keresendő tömböt, a bal és jobb oldali keresési tartomány határait és a keresendő célértéket. A függvény visszaadja az indexét, ha a kívánt érték megtalálható; egyébként -1-et ad vissza.
- A fő függvény létrehoz egy tömböt és egy értékcélt. A binary_search függvény ezután a tömbben a kívánt érték keresésére szolgál. A függvény azt az indexet adja vissza, ahol a célérték található, ha volt, a függvény pedig azt az indexet, amelynél megtalálta. Ellenkező esetben a „Cél nem található” üzenet jelenik meg.
- A bináris keresési algoritmus megvalósítása alapvető. Kezdjük azzal, hogy a bal szegélyt a tömb kezdeti indexére, a jobb oldali határt pedig a tömb utolsó indexére állítjuk. Ha a bal oldali határ kisebb vagy egyenlő, mint a jobb oldali szegély, a tömb még egyszer áthurkolódik. A cikluson belül a (bal + jobb) / 2 képletet használjuk a keresési tartomány középső indexének kiszámításához. Ez a képlet a középső index alsó szintjének egész értékét számítja ki.
- A tömb középső tagját szembeállítjuk a célértékkel. A középső elem indexét adjuk vissza, ha egyenlők. A jobb oldali határt a középső indexnél eggyel kisebbre változtatjuk, ha a kívánt érték kisebb, mint a középső elem. Ha nem, akkor a bal oldali szegélyt úgy állítjuk be, hogy az eggyel több legyen, mint a középső index. Ezt addig folytatjuk, amíg a célértéket meg nem kapjuk, vagy a keresési mező meg nem telik.
- A bináris keresési algoritmus időbeli bonyolultsága, ahol n a tömb mérete, O(log n). Ez sokkal hatékonyabb, mint a lineáris keresés, amelynek időbeli összetettsége O(n), ahol n a tömb mérete.
- Végül a bináris keresési technika hasznos módot kínál egy adott tag megkeresésére egy rendezett tömbben. Könnyen felépíthető, és O(log n) időbonyolultsága van, így hatékony megközelítést jelent nagy adatkészletek esetén.
Előnyök:
- Nagy adathalmazok esetén a bináris keresési algoritmus rendkívül hatékony, és a bemeneti méretek széles skáláját képes kezelni.
- Az algoritmus szinte minden programozási nyelven egyszerűen megvalósítható.
Hátrányok:
- A bináris keresési technika alkalmazása előtt a bemeneti tömböt rendezni kell, ami több időt és memóriát igényel.
- Az algoritmus nem alkalmazható rendezetlen tömbökre.
- Az algoritmus pontatlan eredményeket adhat, ha a bemeneti tömb nincs rendezve.
- A bináris keresési algoritmus nem megfelelő apró adatkészletekhez, mivel a technika többletköltsége meghaladhatja annak előnyeit.
Következtetés:
Egy rendezett tömbben gyorsan meg lehet keresni egy adott elemet a bináris keresési technikával. Oszd meg és uralkodj stratégiát alkalmaz, hogy minden iterációnál felére csökkentse a keresési tartományt, ami lehetővé teszi, hogy nagy adatkészletek esetén rendkívül hatékony legyen. A bináris keresési technika alkalmazása előtt azonban a bemeneti tömböt rendezni kell, ami több időt és memóriát igényel. A bináris keresési algoritmus egy kifinomult adatfeldolgozó eszköz, amelyet széles körben használnak különböző ágazatokban.