Навигация по отсортированным массивам: глубокое погружение в двоичный поиск в Ruby, JavaScript и Python
Двоичный поиск — это алгоритм поиска, который находит положение целевого значения в отсортированном массиве или списке. Он значительно более эффективен, чем линейный поиск, особенно для больших наборов данных, поскольку его временная сложность равна O(log n). Ниже мы рассмотрим, как реализовать двоичный поиск в Ruby, Python и JavaScript.
Алгоритм двоичного поиска
Алгоритм двоичного поиска работает следующим образом:
- Найдите средний элемент массива.
- Если средний элемент равен целевому значению, верните индекс.
- Если целевое значение меньше среднего элемента, повторите поиск с левой половиной массива.
- Если целевое значение больше среднего элемента, повторите поиск с правой половиной массива.
- Если целевое значение отсутствует в массиве, верните -1 или какой-либо индикатор неудачи.
Рубиновая реализация
В Ruby вы можете реализовать двоичный поиск следующим образом:
def binary_search(array, target)
low = 0
high = array.length - 1
while low <= high
mid = (low + high) / 2
if array[mid] == target
return mid
elsif array[mid] < target
low = mid + 1
else
high = mid - 1
end
end
return -1 # Return -1 if target not found
end
Реализация Python
В Python двоичный поиск можно реализовать следующим образом:
def binary_search(array, target):
low = 0
high = len(array) - 1
while low <= high:
mid = (low + high) // 2
if array[mid] == target:
return mid
elif array[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # Return -1 if target not found
Реализация JavaScript
В JavaScript вы можете реализовать двоичный поиск следующим образом:
function binarySearch(array, target) {
let low = 0;
let high = array.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (array[mid] === target) {
return mid;
} else if (array[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Return -1 if target not found
}
Примеры использования
Вот как вы можете использовать функцию двоичного поиска на каждом языке:
Рубин
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] target = 15 puts binary_search(array, target) # Output: 7
Питон
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] target = 15 print(binary_search(array, target)) # Output: 7
JavaScript
let array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]; let target = 15; console.log(binarySearch(array, target)); // Output: 7
Заключение
Двоичный поиск — это высокоэффективный алгоритм поиска в отсортированных массивах или списках с временной сложностью O(log n). Реализация двоичного поиска в разных языках программирования, таких как Ruby, Python и JavaScript, предполагает схожую логическую структуру с небольшими синтаксическими различиями. Понимая основную логику поиска среднего элемента и сужая диапазон поиска, вы можете легко адаптировать реализацию к различным языкам программирования и вариантам использования.
