介绍
二分查找(Binary search)是一种在已排序数组中查找元素索引位置的方法。在 C++ 中,我们可以通过两种方式实现二分查找——迭代(iterative)和递归(recursive)。在本实验中,我们将使用动态数组(dynamic array)来执行二分查找操作。
二分查找(Binary search)是一种在已排序数组中查找元素索引位置的方法。在 C++ 中,我们可以通过两种方式实现二分查找——迭代(iterative)和递归(recursive)。在本实验中,我们将使用动态数组(dynamic array)来执行二分查找操作。
首先,我们在 ~/project
目录下创建一个名为 main.cpp
的 C++ 文件。
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++ 中使用动态数组执行二分查找。我们使用了迭代方法,并实现了一个二分查找函数来在已排序数组中查找元素的索引位置。我们还学习了如何在 C++ 中使用 vector
类创建动态数组。