Алгоритмы поиска и их программа

2.3 ПОИСК В ПРОГРАММИРОВАНИИ БИНАРНЫЙ
Двоичный поиск — (англ.Binary search - двоичный поиск) - эффективный алгоритм поиска элемента из списка отсортированных элементов. Алгоритм двоичного поиска работает на основе парадигмы „разделяй и властвуй“ в соответствии с идеей производительности. Один из наиболее распространенных способов использования двоичного поиска-найти элемент в массиве. Например, звездный каталог Tycho-2 содержит информацию о 2 539 913 самых ярких звездах в нашей галактике. Допустим, вы хотите найти конкретную звезду в каталоге по названию звезды. Если программа проверяла каждую звезду в звездном каталоге, начиная с первой, в алгоритме линейного поиска, в худшем случае компьютеру может потребоваться проверить все 2 539 913 звезд, чтобы найти звезду, которую вы ищете. Если бы каталог был отсортирован в алфавитном порядке по названиям звезд, двоичный поиск не должен был бы проверять более 22 звезд, даже в худшем случае.
Принцип работы алгоритма двоичного поиска:
Попробуем поиграть в игру с компьютером, чтобы понять, как работает алгоритм двоичного поиска.
Условие игры
* Компьютер выбирает произвольное натуральное число между 1 и 100.
• Задача состоит в том, чтобы найти это число, используя как можно меньше предположений.
* После каждого предположения компьютер сообщит вам, является ли ваше предположение больше или меньше числа, выбранного компьютером.
• Если ваше предположение совпадает с числом, выбранным компьютером, игра окончена.
Для чего нужен алгоритм нахождения наименьшего шага?
Сначала мы попытаемся угадать среднее число, то есть 50. Предположим, компьютер сказал нам, что наша оценка меньше числа, выбранного компьютером. Теперь мы знаем, что число, выбранное компьютером, - это число между 51 и 100. Таким образом, наше поле поиска сокращается вдвое (50 чисел). Продолжим таким же образом. Теперь возьмем число между числами от 51 до 100, то есть 75. Компьютер сказал нам, что 75 больше выбранного числа. Это означает, что все числа больше 75 также больше, чем выбранное число. Таким образом, поле поиска у нас снова сократилось вдвое (25 номеров). Продолжая аналогичным образом, мы можем найти мысленное число. В случае чисел 100 мы сможем найти любое приближение максимум за 7 шагов
Программа
#include
using namespace std;
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);

}
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element massivda mavjud emas"
: cout << "Element indeksda mavjud " << result;
return 0;
}