C++ предлагает множество методов поиска для поиска определенной переменной в массиве или какой-либо другой структуре данных. Среди всех них бинарный поиск довольно известен своим быстрым откликом. Массив будет преобразован пополам в рамках бинарного поиска, пока он уже отсортирован. Сравнение будет производиться по средней точке массива. Это среднее значение указывает нам искать требуемое значение в левой половине массива или в правой половине. Половина времени поиска будет сэкономлена при работе с методом бинарного поиска по сравнению с другими методами поиска. Таким образом, в этой простой статье мы обсудим несколько примеров, иллюстрирующих работу бинарного поиска с использованием методов итеративного и рекурсивного поиска.
После быстрого открытия оболочки терминала вам понадобится файл C++, чтобы создать в нем код двоичного поиска. Следовательно, по этой причине будет использоваться простая команда ключевого слова, состоящая из одного слова, т. е. «коснуться». Итак, мы использовали его для создания файла C++ с именем «binary.cc» и открытия его с помощью встроенного редактора GNU Nano, который соответствует конфигурации системы Ubuntu 20.04. Обе команды уже были продемонстрированы с помощью изображения ниже.
Пример 1: Итеративный метод
Самый первый метод, который мы здесь использовали, — это итеративный метод бинарного поиска. Это было бы довольно просто сделать. После того, как файл был открыт в редакторе nano, мы добавили заголовочные файлы, необходимые для запуска кода. Пространство имен, которое должно быть стандартным, здесь необходимо для кода C++. Для выполнения бинарного поиска была создана определяемая пользователем функция под названием «поиск». Эта определяемая пользователем функция принимает в своих параметрах 4 аргумента, то есть «A[]» для массива, left для массивов с крайним левым значением, right для массивов с крайним справа значением и v для значения, которое нужно искать в массиве «A».
В начале этой функции мы использовали простой цикл «пока», чтобы проверить, меньше или равно крайнее левое или первое значение массива крайнему правому значению (введенному последним) массива или нет. Если значение меньше или равно крайнему правому значению, будет создана новая точка в массиве, т. е. середина. Эта средняя точка была рассчитана с использованием как левого, так и правого. После того, как средняя точка найдена, мы используем оператор «if», чтобы проверить, совпадает ли значение в середине индекса массива «A» со значением, запрошенным для проверки, т. е. «v». Если условие стало эффективным и значение «v» совпало со значением среднего индекса, оно вернет средний индекс массива. В начале наш массив имеет две половины, левую и правую. Левый содержит меньшие значения, в то время как правый содержит большие значения по сравнению со средним значением индекса. Когда значение в средней точке меньше искомого значения, нам не нужно рассматривать левую половину массива, потому что она будет содержать меньшие значения.
Итак, мы будем обновлять нашу левую переменную с индексом «mid+1». С другой стороны, если среднее значение больше значения, запрошенного для проверки, нам нужно игнорировать правую половину (большие значения) массива. Таким образом, правая переменная будет обновлена новым значением, т. е. «mid-1». Этот процесс будет продолжаться до тех пор, пока левая часть массива не будет равна или меньше правой точки массива. Если ни одно из условий не выполнено, мы не нашли значение в массиве и возвращаем −1 в качестве индекса для основного метода.
Теперь подошли к реализации функции main(). В этой функции мы объявили массив с именем «A» с некоторыми целыми значениями в нем. Массив уже отсортирован по возрастанию. Затем инициализируется переменная «v», в которой будет сохранено значение, введенное пользователем. Оператор cout говорит пользователю ввести некоторое число, в то время как оператор cin используется для сбора пользовательского ввода и сохранения его в переменной «v».
Другая переменная, «n», была определена для получения общего размера массива с использованием функции sizeof() для массива «A». Другая переменная, «val», использовалась для получения индекса из метода поиска в качестве возвращаемого значения путем его вызова. Вызов функции передает массив A, левую точку как 0, правую точку как целое число «n-1» и значение «v» для поиска. Если метод поиска возвращает «-1» в переменную «val», будет выполнен первый оператор cout; в противном случае будет выполнен второй и отобразится индекс совпавшего значения.
Таким образом, код сначала требует компиляции. После первого и второго выполнения пользователь ввел 14 и 19, и они были сопоставлены с индексами 3 и 8 соответственно, как показано. При третьем выполнении получилось не так, как показано. Итак, компилятор g++ вам в помощь.
Пример 2: рекурсивный метод
Это было все об итеративном методе бинарного поиска в C++. Давайте рассмотрим второй метод бинарного поиска в C++, известный и рекурсивный метод. Рекурсивный метод будет таким же, как итеративный, но рекурсивно вызовет его метод бинарного поиска. Мы объясним это с помощью кода. Итак, откройте тот же файл и обновите метод поиска. Мы использовали один и тот же цикл while в методе поиска с теми же условиями в нем, т. е. операторами if-else, одиночным оператором if и вычислением средней точки.
Единственное изменение было выполнено в операторе if-else функции поиска. Когда значение средней точки больше, чем значение, которое нужно найти в методе поиска, и условие выполнено, он вызовет тот же метод поиска с небольшим изменением его параметров. Все параметры будут такими же, кроме «правильного» значения точки, которое теперь является индексом «mid-1». С другой стороны, когда значение средней точки меньше искомого значения, т. е. «v», и условие не выполняется, будет вызвана та же функция с небольшим изменением аргумента параметра «left». Теперь левая точка будет обновлена с индексом «mid+1».
Вы можете видеть, что функция main() на 100% такая же, как в приведенном выше итеративном примере, и в ней нет ни одного изменения символа.
Сначала скомпилируйте этот обновленный рекурсивный код с помощью g++, а затем выполните его. После первого выполнения возвращает 3 в качестве результата для значения 14, тогда как для значения 24 после второго выполнения индекс пока не найден.
Завершение
Вся вышеприведенная статья посвящена бинарному поиску в C++. Бинарный поиск был обнаружен и хорошо объяснен двумя различными методами, т. е. итеративным и рекурсивным. Все реализованные и продемонстрированные примеры довольно просты в исполнении и понятны, так как каждый шаг объяснен довольно кратко. Поэтому мы возлагаем большие надежды, что эта статья будет одинаково полезна и наивному, и новому, и опытному пользователю.
