Difference between revisions 18362858 and 19103329 on ukwiki

 {{Приєднати до|Алгоритми пошуку в масиві|дата=травень 2014}}
== Лінійний пошук ==
<big>''Лінійний пошук''</big> - [[алгоритм]] послідовного пошуку знаходження заданого елемента в деякому [[масив даних|масиві]]. Цей алгоритм є найпростішим алгоритмом пошуку і на відміну від двійкового пошуку, не накладає жодних обмежень на масив і має просту реалізацію. У зв'язку з малою ефективністю в порівнянні з іншими алгоритмами лінійний пошук зазвичай використовують лише тоді, коли відрізок пошукової системи містить дуже мало елементів, однак лінійний пошук не вимагає додаткової пам'яті або обробки/аналізу масиву.
=== Приклад коду ===
Тут ''lenghtOfArr'' - це довжина деякого масиву, ''key'' - значення яке ми шукаємо, якщо елемент масиву співпадаєзбігається з значенням ''key'' повертаємо ''true''. Суть методу полягає в тому що ми поелементно перебираємо масив до тих пір поки умова в операторі ''if'' не буде виконана.<br />

   for (int i=0; i<lenghtOfArr ;i++)
        {
            if (Arr[i]==key)
                {
                     return true;
                }
        }

== Дихотомічний пошук (двійковий пошук) ==
<big>''Дихотомічний пошук (двійковий пошук)''</big> — [[алгоритм]] знаходження заданого значення у ''впорядкованому'' [[масив даних|масиві]], який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини, залежно від результату порівняння. Зазвичай реалізується методом рекурсії, або ітерації. Основна вимога до масиву-''впорядкованість''.
=== Приклад коду ===
Дихотомічний пошук рекурсивним методом
 BinarySearch(A[0..N-1], value, low, high) {
     if (high < low)<br />
         return -1 // не знайдено
     mid = (low + high) / 2
     if (A[mid] > value)
         return BinarySearch(A, value, low, mid-1)
     else if (A[mid] < value)
         return BinarySearch(A, value, mid+1, high)
     else
         return mid // знайдено
   }

== Див. також ==
[[Алгоритм сортування]]<br />
[[Список алгоритмів]]

== Джерела ==
Вірт Н. (1985), Алгоритми та структури даних

http://emerecu.ukma.kiev.ua/books/PROG/ABU/abut7.htm
[[Категорія:Теорія алгоритмів]]