C++ 使用动态数组实现二分查找

C++C++Beginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

介绍

二分查找(Binary search)是一种在已排序数组中查找元素索引位置的方法。在 C++ 中,我们可以通过两种方式实现二分查找——迭代(iterative)和递归(recursive)。在本实验中,我们将使用动态数组(dynamic array)来执行二分查找操作。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("C++")) -.-> cpp/BasicsGroup(["Basics"]) cpp(("C++")) -.-> cpp/IOandFileHandlingGroup(["I/O and File Handling"]) cpp(("C++")) -.-> cpp/SyntaxandStyleGroup(["Syntax and Style"]) cpp(("C++")) -.-> cpp/ControlFlowGroup(["Control Flow"]) cpp(("C++")) -.-> cpp/FunctionsGroup(["Functions"]) cpp(("C++")) -.-> cpp/StandardLibraryGroup(["Standard Library"]) cpp/BasicsGroup -.-> cpp/data_types("Data Types") cpp/BasicsGroup -.-> cpp/arrays("Arrays") cpp/ControlFlowGroup -.-> cpp/conditions("Conditions") cpp/ControlFlowGroup -.-> cpp/while_loop("While Loop") cpp/FunctionsGroup -.-> cpp/function_parameters("Function Parameters") cpp/IOandFileHandlingGroup -.-> cpp/output("Output") cpp/IOandFileHandlingGroup -.-> cpp/files("Files") cpp/StandardLibraryGroup -.-> cpp/standard_containers("Standard Containers") cpp/SyntaxandStyleGroup -.-> cpp/code_formatting("Code Formatting") subgraph Lab Skills cpp/data_types -.-> lab-96172{{"C++ 使用动态数组实现二分查找"}} cpp/arrays -.-> lab-96172{{"C++ 使用动态数组实现二分查找"}} cpp/conditions -.-> lab-96172{{"C++ 使用动态数组实现二分查找"}} cpp/while_loop -.-> lab-96172{{"C++ 使用动态数组实现二分查找"}} cpp/function_parameters -.-> lab-96172{{"C++ 使用动态数组实现二分查找"}} cpp/output -.-> lab-96172{{"C++ 使用动态数组实现二分查找"}} cpp/files -.-> lab-96172{{"C++ 使用动态数组实现二分查找"}} cpp/standard_containers -.-> lab-96172{{"C++ 使用动态数组实现二分查找"}} cpp/code_formatting -.-> lab-96172{{"C++ 使用动态数组实现二分查找"}} end

创建一个新的 C++ 文件

首先,我们在 ~/project 目录下创建一个名为 main.cpp 的 C++ 文件。

touch ~/project/main.cpp

包含头文件

接下来,我们包含必要的头文件——iostreamalgorithmvector

#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++ 中使用动态数组执行二分查找。我们使用了迭代方法,并实现了一个二分查找函数来在已排序数组中查找元素的索引位置。我们还学习了如何在 C++ 中使用 vector 类创建动态数组。