Алгоритм двоичного поиска используется для нахождения индекса заданного элемента в отсортированном массиве.
Давайте посмотрим на следующий пример:
Input: arr[] = {10, 20, 30, 50, 60, 80, 110, 130, 140, 170}
x = 110
Output: 6
Explanation: Element x is present at index 6.
Есть ли другой подход вместо бинарного поиска?
Линейный поиск — это еще один метод поиска заданного значения в массиве. Он будет проходить по элементу массива за элементом и искать, существует ли элемент в массиве или нет. Временная сложность линейного поиска составляет O(n). Мы рассмотрим временную сложность в следующей статье.
Двоичный поиск — это алгоритм поиска, используемый в отсортированном массиве путем неоднократного деления интервала поиска пополам. Временная сложность бинарного поиска составляет O(Log n).
Ниже приведены основные шаги для выполнения бинарного поиска:
- массив должен быть отсортирован
2. установите Нижний индекс -> Первый элемент массива и Верхний индекс -> Последний элемент массива.
3. Установите средний индекс -› среднее значение низких и высоких индексов(Низкий + Высокий)/2
4. Если элемент в среднем индексе является целевым значением, верните средний индекс
5. Если целевой элемент меньше, чем элемент со средним индексом, установите Высокий индекс -> (Средний индекс-1)
6. Если целевой элемент больше, чем элемент со средним индексом, установите Нижний индекс -> (Средний индекс+1).
7. Повторяйте шаги с 3 по 6, пока мы не получим значение индекса или, если элемент не существует, мы должны вернуть -1.
Есть 2 способа выполнить бинарный поиск;
- Итерационный метод
- Рекурсивный метод
Вы можете задаться вопросом, что это за 2 пути. Давайте посмотрим на это подробно.
- Итерационный метод следует подходу «Уменьшить и победить», где для каждой итерации размер входных данных уменьшается, а затем обрабатывается процесс решения.
Ниже приведен псевдокод для итеративного метода:
binarySearch(arr, target, low, high)
// here we will calculte the low and high values
repeat till low <= high
mid = (low + high)/2
if (target == arr[mid])
return mid
else if (target > arr[mid]) // targetis on the right side
low = mid + 1
else // targetis on the left side
high = mid - 1
2. Рекурсивный метод следует подходу «разделяй и властвуй», когда входные данные делятся на подзадачи, а затем процесс обрабатывается для поиска решения.
Ниже приведен псевдокод для рекурсивного метода:
binarySearch(arr, target, low, high)
if low > high
return False
else
mid = (low + high) / 2
if target== arr[mid]
return mid
else if target> arr[mid] // target is on the right side
return binarySearch(arr, target, mid + 1, high)
else // targetis on the left side
return binarySearch(arr, target, low, mid - 1)
Теперь давайте посмотрим реализации JavaScript для обоих методов.
- Итеративный метод:
function binarySearch(arr, target) {
let low= 0;
let high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // if target not found
}
// Example usage:
const arr = [1, 3, 4, 6, 7, 8, 9];
const target = 4;
const index = binarySearch(arr, target); // returns 2
Итерация должна быть остановлена, когда нижний индекс превосходит или превышает высокий индекс.
2. Рекурсивный метод:
function binarySearch(arr, l, r, x){
if (r >= l) {
let mid = l + Math.floor((r - l) / 2);
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
let arr = [ 2, 3, 4, 10, 40 ];
let x = 10;
let n = arr.length
let index = binarySearch(arr, 0, n - 1, x);
Вот и все.. надеюсь, вам понравилось.
