TechCodeview

Rýchla metóda na nájdenie konkrétneho prvku v zoradenom poli je binárne vyhľadávanie. Prvotnou úlohou tohto algoritmu je porovnať cieľovú hodnotu so stredným prvkom poľa. Vyhľadávanie sa považuje za úspešné, ak je cieľová hodnota obsiahnutá v strednom prvku. Algoritmus bude hľadať v ľavej polovici poľa, ak je cieľová hodnota menšia ako stredný prvok. Ak je cieľová hodnota väčšia ako stredný prvok, program naskenuje pravú polovicu poľa. Táto metóda sa opakuje, kým sa nevyčerpá cieľová hodnota alebo rozsah vyhľadávania.

Použitie:

Databázy, vyhľadávače a spracovanie údajov sú len niektoré z aplikácií, ktoré využívajú stratégiu binárneho vyhľadávania.

podčiarknuť v značke

Charakteristika:

• Pole vstupných hodnôt musí byť zoradené.
• Pri každej iterácii metóda zmenšuje rozsah vyhľadávania na polovicu, čím je obzvlášť efektívna pre veľké súbory údajov.
• Algoritmus má O (log n) časovú zložitosť najhoršieho prípadu.
• Nájdenie požadovanej hodnoty program vykoná pomocou stratégie rozdeľuj a panuj.

Tu je jednoduchý príklad binárneho vyhľadávacieho algoritmu napísaného v C:

nataša dala

 #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></=>

• Funkcia binary_search akceptuje štyri argumenty: pole na vyhľadávanie, ľavé a pravé hranice rozsahu vyhľadávania a cieľovú hodnotu, ktorú treba hľadať. Funkcia vráti svoj index, ak je možné nájsť požadovanú hodnotu; inak vráti -1.
• Hlavná funkcia vytvára pole arr a cieľovú hodnotu. Funkcia binary_search sa potom použije na vyhľadanie poľa pre požadovanú hodnotu. Funkcia vráti index, kde sa nachádzala cieľová hodnota, ak bola, funkcia vráti index, na ktorom bola nájdená. V opačnom prípade sa zobrazí správa „Cieľ nenájdený“.
• Implementácia binárneho vyhľadávacieho algoritmu je základná. Začneme nastavením ľavého okraja na počiatočný index poľa a pravého okraja na posledný index poľa. Keď je ľavá hranica menšia alebo rovná pravému okraju, pole sa pretočí ešte raz. Na výpočet stredného indexu rozsahu vyhľadávania používame vzorec (vľavo + vpravo) / 2 v rámci cyklu. Tento vzorec vypočíta celočíselnú hodnotu spodnej hranice stredného indexu.
• Stredový člen poľa je v kontraste s cieľovou hodnotou. Vrátime index stredného prvku, ak sú rovnaké. Pravú hranicu zmeníme tak, aby bola o jednu menšiu ako je stredný index, ak je požadovaná hodnota menšia ako stredný prvok. Ak nie, upravíme ľavý okraj tak, aby bol o jeden viac ako stredový index. Pokračujeme v tom, kým nezískame cieľovú hodnotu alebo nevyplníme vyhľadávací priestor.
• Časová zložitosť binárneho vyhľadávacieho algoritmu, kde n je veľkosť poľa, je O(log n). Toto je oveľa efektívnejšie ako lineárne vyhľadávanie, ktoré má dočasnú zložitosť O(n), kde n je veľkosť poľa.
• Nakoniec, technika binárneho vyhľadávania ponúka užitočný spôsob, ako nájsť konkrétneho člena v triedenom poli. Je ľahko zostaviteľný a má časovú zložitosť O(log n), čo z neho robí efektívny prístup pre veľké súbory údajov.

Výhody:

• Pre veľké súbory údajov je binárny vyhľadávací algoritmus výnimočne efektívny a je schopný spracovať širokú škálu vstupných veľkostí.
• Algoritmus je jednoduchý na implementáciu takmer vo všetkých programovacích jazykoch.

Nevýhody:

• Pred použitím techniky binárneho vyhľadávania je potrebné triediť vstupné pole, čo si vyžaduje viac času a pamäte.
• Algoritmus nemožno použiť na nezoradené polia.
• Algoritmus môže poskytnúť nepresné výsledky, ak nie je zoradené vstupné pole.
• Algoritmus binárneho vyhľadávania nie je vhodný pre malé súbory údajov, pretože réžia techniky môže prevážiť jej výhody.

Záver:

Zoradené pole možno rýchlo vyhľadať konkrétny prvok pomocou techniky binárneho vyhľadávania. Využíva stratégiu rozdelenia a panovania na zníženie rozsahu vyhľadávania na polovicu pri každej iterácii, čo umožňuje, aby bol vysoko efektívny pre veľké súbory údajov. Pred použitím techniky binárneho vyhľadávania je však potrebné triediť vstupné pole, čo si vyžaduje viac času a pamäte. Binárny vyhľadávací algoritmus je sofistikovaný nástroj na spracovanie údajov, ktorý je široko používaný v rôznych sektoroch.