Двоичный поиск в C++ с использованием динамического массива

Введение

Двоичный поиск - это метод поиска, который находит индекс элемента в отсортированном массиве. В C++ мы можем выполнить двоичный поиск двумя способами - итеративным и рекурсивным. В этом лабораторном задании мы выполним операцию двоичного поиска с использованием динамического массива.

Создайте новый файл на C++

Сначала мы создаем новый файл на C++ в директории ~/project с именем main.cpp.

touch ~/project/main.cpp

Подключите заголовочные файлы

Далее мы подключаем необходимые заголовочные файлы - iostream, algorithm и vector.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

Создайте динамический массив и заполните его элементами

Мы создаем динамический массив целых чисел с использованием класса vector и заполняем его отсортированными целыми числами.

vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};

Реализуйте функцию двоичного поиска

Далее мы реализуем функцию двоичного поиска, которая ищет индекс элемента в отсортированном массиве с использованием итеративного подхода.

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

Вызовите функцию двоичного поиска и выведите результат

Наконец, мы вызываем функцию двоичного поиска с элементом для поиска и выводим результат в консоль.

int target = 7;
int result = binarySearch(arr, target);

if (result == -1) {
    cout << "Element not found!" << endl;
} else {
    cout << "Element found at index " << result << endl;
}

Компилируйте и запустите программу

Скомпилируйте и выполните программу в терминале, выполнив следующую команду:

g++ main.cpp -o main &&./main

Конечный код

Вот полный код файла main.cpp:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;
    int result = binarySearch(arr, target);

    if (result == -1) {
        cout << "Element not found!" << endl;
    } else {
        cout << "Element found at index " << result << endl;
    }

    return 0;
}

Резюме

В этом практическом занятии мы узнали, как выполнять двоичный поиск с использованием динамического массива в C++. Мы использовали итеративный подход и реализовали функцию двоичного поиска для поиска индексного положения элемента в отсортированном массиве. Мы также узнали, как создавать динамический массив с использованием класса vector в C++.