Привет, это # Day_6, мы собираемся поговорить о Двоичный поиск алгоритм Отказ
Определение двоичного алгоритма поиска
Бинарный поиск Также называется Поиск половины интервала или Логарифмический поиск является одним из самых известных алгоритмов поиска,
Этот алгоритм ищет отсортированного массива, повторно разделяя интервал поиска пополам. Начните с интервала, покрывающего весь массив. Если значение ключа поиска меньше элемента в середине интервала, сузмещайте интервал на нижнюю половину. В противном случае сузьте его до верхней половины. Повторно проверяйте, пока значение не найдено или интервал пуст.
Сложность пространства и времени
Космическая сложность линейного поиска – O (1) И его временная сложность – O (log n) Отказ
Реализация двоичного поиска в Python
def BinarySearchAlgorithm(wantedItem: int, sortedItems: list):
"""
=> Algorithm Name : Binary Search
=> Algorithm Type : Searching Algorithms
=> Time Complexity : O(n)
=> Space Complexity : O(1)
=> Logic
[ if wantedItem == mid ]
[ if wantedItem < sortedItems[mid] ] eliminate right half
[ if wantedItem > sortedItems[mid] ] eliminate left half
=> Arguments
[wantedItem]{int}
[sortedItems] {list} sorted list
=> Returns
[index] if the wanted item exists in the list
[False] if the wanted item doesn't exist in the list
"""
low = 0
high = len(sortedItems) - 1
while low <= high :
mid = (high + low) // 2
if wantedItem == sortedItems[mid]:
return mid
elif wantedItem > sortedItems[mid]:
# eliminate left half
low = mid + 1
else:
# eliminate right half
hight = mid - 1
# if the item dosen't exist
return False
Реализация двоичного поиска в JavaScript
/**
* binary search algorithm
* Time Complexity: O(log n)
* Space Complexity: O(1)
* @param wantedItem {Number} the desired element
* @param sortedItems {Array} sorted array of numbers
* @returns {(Number|Boolean)} (wantedItem) index if it exist otherwise (false)
*/
const BinarySearchAlgorithm = (wantedItem, sortedItems) => {
let low = 0,
high = items.length,
mid;
while (low <= high) {
// the mid can be a float num that's why I used Math.floor
mid = Math.floor((high + low) / 2);
if (wantedItem == items[mid]) return mid;
if (wantedItem < items[mid]) {
// eliminate right half
high = mid - 1;
} else {
// eliminate left half
low = mid + 1;
}
}
// if the wanted item dosen't exist
return false;
};
Большое вам спасибо за ваше время! Хорошего дня; # день_6.
Оригинал: “https://dev.to/ayabouchiha/binary-search-algorithm-32ki”