TechCodeview

Бърз метод за намиране на определен елемент в сортиран масив е двоично търсене. Първоначалната задача на този алгоритъм е да сравни целевата стойност със средния елемент на масива. Търсенето се счита за успешно, ако целевата стойност се съдържа в средния елемент. Алгоритъмът ще търси в лявата половина на масива, ако целевата стойност е по-малка от централния елемент. Програмата ще сканира дясната половина на масива, ако целевата стойност е по-голяма от централния елемент. Този метод се повтаря до изчерпване на целевата стойност или обхвата на търсене.

Употреба:

Базите данни, търсачките и обработката на данни са само малка част от приложенията, които използват стратегията за двоично търсене.

Характеристики:

• Масивът от входни стойности трябва да бъде сортиран.
• С всяка итерация методът свива обхвата на търсене наполовина, което го прави особено ефективен за огромни набори от данни.
• Алгоритъмът има O (log n) времева сложност за най-лошия случай.
• Намирането на желаната стойност се извършва от програмата с помощта на стратегия „разделяй и владей“.

Ето директен пример за алгоритъм за двоично търсене, написан на 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 &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></=>

• Функцията binary_search приема четири аргумента: масива за търсене, лявата и дясната граница на обхвата на търсене и целевата стойност за търсене. Функцията връща своя индекс, ако желаната стойност може да бъде намерена; в противен случай връща -1.
• Основната функция създава масив arr и целева стойност. След това функцията binary_search се използва за търсене в масива за желаната стойност. Функцията връща индекса, където се намира целевата стойност, ако е била, функцията връща индекса, на който е намерена. В противен случай се показва съобщението „Целта не е намерена“.
• Изпълнението на алгоритъма за двоично търсене е основно. Започваме, като зададем лявата граница на началния индекс на масива и дясната граница на последния индекс на масива. След като лявата граница е по-малка или равна на дясната граница, масивът се преминава през още веднъж. Използваме формулата (ляво + дясно) / 2 в рамките на цикъла, за да изчислим средния индекс на диапазона на търсене. Тази формула изчислява целочислената стойност на дъното на средния индекс.
• Централният член на масива е в контраст с целевата стойност. Връщаме индекса на средния елемент, ако са равни. Променяме дясната граница да бъде с едно по-малко от средния индекс, ако желаната стойност е по-малка от средния елемент. Ако не, коригираме лявата граница, така че да е с една повече от централния индекс. Продължаваме да правим това, докато се получи целевата стойност или се запълни полето за търсене.
• Времевата сложност на алгоритъма за двоично търсене, където n е размерът на масива, е O(log n). Това е много по-ефективно от линейното търсене, което има времева сложност O(n), където n е размерът на масива.
• И накрая, техниката за двоично търсене предлага полезен начин за намиране на определен член в сортиран масив. Той е лесен за изграждане и има времева сложност O(log n), което го прави ефективен подход за големи масиви от данни.

Предимства:

• За големи масиви от данни алгоритъмът за двоично търсене е изключително ефективен и е способен да обработва широк диапазон от входни размери.
• Алгоритъмът е лесен за изпълнение в почти всички езици за програмиране.

Недостатъци:

• Преди да използвате техниката за двоично търсене, входният масив трябва да бъде сортиран, което отнема повече време и памет.
• Алгоритъмът не може да се прилага към несортирани масиви.
• Алгоритъмът може да даде неточни резултати, ако входният масив не е сортиран.
• Алгоритъмът за двоично търсене не е подходящ за малки набори от данни, тъй като режийните разходи на техниката може да надхвърлят предимствата.

Заключение:

В сортиран масив може бързо да се търси конкретен елемент, като се използва техниката за двоично търсене. Той използва стратегия „разделяй и владей“, за да намали обхвата на търсене наполовина с всяка итерация, което му позволява да бъде много ефективен за големи набори от данни. Въпреки това, преди да се използва техниката за двоично търсене, входният масив трябва да бъде сортиран, което отнема допълнително време и памет. Алгоритъмът за двоично търсене е усъвършенстван инструмент за обработка на данни, който се използва широко в различни сектори.