Общий принцип
- Начните со среднего элемента:Если целевое значение равно среднему элементу массива, то верните индекс среднего элемента.
Если нет, то сравните средний элемент с целевым значением,Если целевое значение больше числа в среднем индексе, то выберите элементы справа от среднего индекса и начните с шага 1.
Если целевое значение меньше числа в среднем индексе, то выберите элементы слева от среднего индекса и начните с шага 1. - Когда совпадение найдено, верните индекс соответствующего элемента.
- Если совпадение не найдено, верните значение -1
Пример:
Давайте посмотрим как работает бинарный поиск на примере.В примере ниже в строке 9 мы создали массив arr на 10 элементов и в строке 12 предложили пользователю с клавиатуры заполнить его ячейки.
В строке 20 мы предлагаем пользователю ввести ключ (который нужно будет найти в массиве), а дальше мы с бинарным поиском проверим массив на наличие введенного ключа пользователем. Если мы найдем ключ в массиве, то выведем индекс ячейки, в которой находится ключ.
#include <iostream> #include <algorithm>
using namespace std;
int main() { setlocale(LC_ALL, "rus");
int arr[10]; // создали массив на 10 элементов int key; // создали переменную в которой будет находиться ключ
cout << "Введите 10 чисел для заполнения массива: " << endl;
for (int i = 0; i < 10; i++) { cin >> arr[i]; // считываем элементы массива }
sort (arr, arr + 10); // сортируем с помощью функции sort (быстрая сортировка)
cout << endl << "Введите ключ: ";
cin >> key; // считываем ключ
bool flag = false; int l = 0; // левая граница int r = 9; // правая граница int mid;
while ((l <= r) && (flag != true)) { mid = (l + r) / 2; // считываем срединный индекс отрезка [l,r]
if (arr[mid] == key) flag = true; //проверяем ключ со серединным элементом if (arr[mid] > key) r = mid - 1; // проверяем, какую часть нужно отбросить else l = mid + 1; }
if (flag) cout << "Индекс элемента " << key << " в массиве равен: " << mid; else cout << "Извините, но такого элемента в массиве нет";
system("pause"); return 0; }
Бинарный поиск находится в строках 29 - 35. В строке 27 мы создали переменную mid, в которой будет храниться индекс среднего элемента (из отрезка [l, r]). В строке 27 считываем средний элемент отрезка [l, r] в переменную mid, по формуле: (l + r) / 2 (в которой l - левая граница, r - правая граница). В строке 29 проверяем условие arr[mid] == key:
- Если результат условия равен true, то булевой переменной flag присваиваем значение true (это значит, что мы нашли ключ).
В строке 30 мы проверяем условие arr[mid] > key:
- Если значение arr[mid] больше ключа, то переменной r присваиваем значение mid. Потому что проверять верхнюю часть не имеет смысла, так как ключ может находится только в ячейках ниже индекса mid (это если массив отсортирован по возрастанию).
- Если значение arr[mid] меньше ключа, то переменной l присваиваем значение mid. Потому что проверять нижнюю часть не имеет смысла, так как ключ может находится только в ячейках выше индекса mid (это если массив отсортирован по возрастанию).
В строке 37 мы проверяем flag:
- Если flag равен true, значит мы нашли ключ, а значит выводим “Индекс элемента key в массиве равен mid“.
- Если flag равен false, то выводим “Извините, но такого элемента в массиве нет”.
Давайте выполним этот код:
Напишите 10 чисел для заполнения массива:
17 20 26 31 44 54 55 65 77 93
Введите ключ : 54
Индекс элемента 54 в массиве равен: 5
Process returned 0 (0x0) execution time : 0.005 s
Press any key to continue.
А если такого ключа нет в массиве :
Напишите 10 чисел для заполнения массива:
17 20 26 31 44 54 55 65 77 93
Введите ключ : 18
Извините, но такого элемента в массиве нет
Process returned 0 (0x0) execution time : 0.005 s
Press any key to continue.
источник: https://codelessons.dev/ru/binarnyj-poisk-po-massivu-c/
Бинарный поиск через итерацию
#include <bits/stdc++.h>
using namespace std;
// Iretative Binary Search function to find the index of an
// element 'x' in a sorted array 'arr' if elements is
// present, otherwise it return -1
// low: The index of the first element in the current
// sub-array high: The index of the last element in the
// current sub-array
int binarySearch(int arr[], int low, int high, int x)
{
while (low <= high) {
int mid = low + (high - low) / 2;
// If the middle element is equal to 'x', we have
// found the element, return its index
if (arr[mid] == x)
return mid;
// If the middle element is smaller than 'x', search
// in the right half of the array
if (arr[mid] < x)
low = mid + 1;
// If the middle element is greater than 'x', search
// in the left half of the array
else
high = mid - 1;
}
// If the base case is reached, the element is not
// present in the array, return -1
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
// Element to be searched
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
Бинарный поиск через рекурсию
// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
// Recursive Binary Search function to find the index of an
// element 'x' in a sorted array 'arr' if elements is
// present, otherwise it return -1
// low: The index of the first element in the current
// sub-array high: The index of the last element in the
// current sub-array
int binarySearch(int arr[], int low, int high, int x)
{
// Base case: If the search space becomes empty, the
// element is not present in the array
if (high >= low) {
// Calculate the middle index to divide the search
// space in half
int mid = low + (high - low) / 2;
// If the middle element is equal to 'x', we have
// found the element, return its index
if (arr[mid] == x)
return mid;
// If the middle element is greater than 'x', search
// in the left half of the array
if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);
// If the middle element is less than 'x', search in
// the right half of the array
return binarySearch(arr, mid + 1, high, x);
}
// If the base case is reached, the element is not
// present in the array, return -1
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
// Element to be searched
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
источники
Бинарный поиск по ответу
Бинарный поиск по ответу - это алгоритм, в котором мы находим наш ответ с помощью некоторых определенных условий. Мы предоставили пространство поиска, в котором мы берем элемент [mid] и проверяем его достоверность в качестве нашего ответа, если он удовлетворяет заданному нами условию в задаче, тогда мы сохраняем его значение и соответственно сокращаем пространство поиска.
Задача: найти максимальное положительное целое число, удовлетворяющее данному уравнению: n2 < X
Входные данные: X = 101
Результат: 10
- Возьмем n = 50: 502 > 101 , ans = 0 , нижний предел = 0 и верхний предел = 49 ( потому что мы знаем, что если 50 не удовлетворяет нашему уравнению , то значения, превышающие 50 , не дадут нам правильного ответа).
- Принимаем n = 25 (среднее значение нижнего предела). и высоким пределом.) : 252 < 101 , ans = 0 , нижний предел = 0 и верхний предел = 24.
- Принимаем n = 12: 122 < 101 , ans = 0 , нижний предел = 0 и верхний предел = 11.
- Принимая n = 5: 52 < 101 , ans = 5 , нижний предел = 6 и верхний предел = 11 (поскольку мы знаем, что если n = 5 удовлетворяют уравнению, то значения меньше 5 также дают правильный ответ).
- Принимаем n = 8: 82 < 101 , ans = 8 , нижний предел = 9 и верхний предел = 11 .
- Принимаем n = 10: 102 < 101 , ans = 10 , нижний предел = 11 и верхний предел = 11.
- Принимаем n = 11: 112 < 101 , ans = 10 , нижний предел = 11 и верхний предел = 10.
Источник :https://www.geeksforgeeks.org/binary-search-on-answer-tutorial-with-problems/
