Двійковий пошук це техніка пошуку, яка працює на Підхід «Розділяй і володарюй». . Він використовується для пошуку будь-якого елемента в сортованому масиві. Порівняно з лінійним, двійковий пошук набагато швидший із часовою складністю O(logN), тоді як лінійний пошук працює з O(N) часовою складністю
Приклади :
Input : arr[] = {1, 3, 5, 7, 8, 9}, x = 5 Output : Element found! Input : arr[] = {1, 3, 5, 7, 8, 9}, x = 6 Output : Element not found!> Примітка: Припускаючи, що масив відсортовано.
випадкове число c код
Ось такі способи виконання двійкового пошуку в JavaScript:
Зміст
Рекурсивний підхід:
- БАЗОВА УМОВА: Якщо початковий індекс більший за кінцевий, повертає false.
- Обчисліть середній індекс.
- Порівняйте середній елемент із числом х. Якщо дорівнює, повертає true.
- Якщо більше, викличте ту саму функцію з кінцевим індексом = middle-1 і повторіть крок 1.
- Якщо менше, викличте ту саму функцію з початковим індексом = middle+1 і повторіть крок 1.
приклад: Цей приклад демонструє використання описаного вище підходу.
javascript
let recursiveFunction =>function> (arr, x, start, end) {> >// Base Condition> >if> (start>кінець)>return> false>;> >// Find the middle index> >let mid = Math.floor((start + end) / 2);> >// Compare mid with given key x> >if> (arr[mid] === x)>return> true>;> >// If element at mid is greater than x,> >// search in the left half of mid> >if> (arr[mid]>x)> >return> recursiveFunction(arr, x, start, mid - 1);> >else> >// If element at mid is smaller than x,> >// search in the right half of mid> >return> recursiveFunction(arr, x, mid + 1, end);> }> // Driver code> let arr = [1, 3, 5, 7, 8, 9];> let x = 5;> if> (recursiveFunction(arr, x, 0, arr.length - 1)) {> >console.log(>'Element found!'>);> }> else> { console.log(>'Element not found!'>); }> x = 6;> if> (recursiveFunction(arr, x, 0, arr.length - 1)) {> >console.log(>'Element found!'>);> }> else> { console.log(>'Element not found!'>); }> |
>
>Вихід
Element found! Element not found!>
Часова складність: O(logN)
Допоміжний простір: О(1)
Ітеративний підхід:
У цьому ітераційному підході замість рекурсії ми використовуємо цикл while, і цикл виконується, доки не досягне базової умови, тобто початок стане більшим за кінець.
приклад: Цей приклад демонструє використання описаного вище підходу.
javascript
// Iterative function to implement Binary Search> let iterativeFunction =>function> (arr, x) {> >let start = 0, end = arr.length - 1;> >// Iterate while start not meets end> >while> (start <= end) {> >// Find the mid index> >let mid = Math.floor((start + end) / 2);> >// If element is present at> >// mid, return True> >if> (arr[mid] === x)>return> true>;> >// Else look in left or> >// right half accordingly> >else> if> (arr[mid] start = mid + 1; else end = mid - 1; } return false; } // Driver code let arr = [1, 3, 5, 7, 8, 9]; let x = 5; if (iterativeFunction(arr, x, 0, arr.length - 1)) { console.log('Element found!'); } else { console.log('Element not found!'); } x = 8; if (iterativeFunction(arr, x, 0, arr.length - 1)) { console.log('Element found!'); } else { console.log('Element not found!'); }> |
>
>Вихід
Element found! Element found!>
Часова складність: O(logN).
Допоміжний простір: О(1)