Бинарный поиск - алгоритм поиска объекта по заданному признаку в множестве ему подобных.
Бинарный поиск отбирает половину последовательности данных на каждом этапе до тех пор, пока не обнаружит искомое или проверит всю последовательность данных.
Каждый раз отбирается объект в середине диапазона отсортированных данных и сравнивается с искомым объектом.
Если они равны, возвращается позиция отобранного объекта, иначе - исключается половина элементов в зависимости от разницы величин отобранного и искомого объектов.
Вычислительная сложность алгоритма равна O(logN), потому что алгоритм выбирает половину последовательности данных на каждом этапе.
Есть некоторая отсортированная последовательность данных:
И объект, позицию которого нужно найти:
Необходимо выбрать объект из середины последовательности.
Нужно сравнить выбранный объект с искомым
Необходимо выбрать часть объектов последовательности, исходя из результата сравнения. В данном случае объект из середины последовательности больше выбранного, поэтому нужно выбрать все объекты, которые меньше взятого.
Совершается та же последовательность действий, пока не останется один объект.
Если оставшийся объект не является искомым, алгоритм передаёт пустое значение, иначе - передаёт позицию найденного объекта.
В данном случае искомый объект найден после завершения второго цикла работы.
// search_element - искомый элемент
функция bin_search(array, search_element)
// индексы начала и конца массива
begin <- 0
end <- длина array
// пока начало массива меньше конца
пока begin <= end
middle_element <- средний элемент массива
если search_element == middle_element
то вернуть индекс middle_element
если search_element < middle_element
// увеличиваем индекс начала массива на половину
то begin = индекс middle_element + 1
если search_element < middle_elemen
// уменьшаем индекс конца массива на половину
то end = индекс end - 1
если search_element нет в массиве
то вернуть -1
def bin_search(array, data):
begin = 0
end = len(array) - 1
while begin <= end:
middle = (begin + end) // 2
guess = array[middle]
if guess == data:
return middle
if guess < data:
begin = middle + 1
else:
end = middle - 1
return -1
template <typename T>
int bin_search(std::vector<T> array, T data) {
int begin = 0;
int end = array.size() - 1;
while (begin <= end) {
int middle = (begin + end) / 2;
T guess = array[middle];
if (guess == data) {
return middle;
}
if (guess < data) {
begin = middle + 1;
}
else {
end = middle - 1;
}
}
return -1;
}
int bin_search_olympic(vector<int> arr, int i) {
int begin = 0;
int end = arr.size() - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (arr[mid] == i) {
return mid;
}
if (arr[mid] < i) {
begin = mid + 1;
}
else {
end = mid - 1;
}
}
return -1;
}