C++ 二分法查找算法
时间: 2023-11-10 13:49:14 浏览: 59
二分法查找算法是一种在有序数组中查找特定元素的算法。它的基本思想是通过将数组不断地分成两半,然后确定目标元素可能存在的区间,直到找到目标元素或确定目标元素不存在。
具体的步骤如下:
1. 首先,将待查找的数组按照从小到大的顺序进行排序。
2. 初始化两个指针,一个指向数组的起始位置,一个指向数组的结束位置。
3. 计算数组中间元素的索引,即 (start + end) / 2。
4. 将中间元素与目标元素进行比较:
- 如果中间元素等于目标元素,则找到了目标元素,返回索引。
- 如果中间元素大于目标元素,则目标元素可能在左半部分,更新结束指针为中间元素的前一个位置。
- 如果中间元素小于目标元素,则目标元素可能在右半部分,更新起始指针为中间元素的后一个位置。
5. 重复步骤 3 和步骤 4,直到找到目标元素或确定目标元素不存在(即起始指针大于结束指针)。
二分法查找算法的时间复杂度为 O(log n),其中 n 是数组的长度。它是一种高效的查找算法,适用于有序数组。
相关问题
用c++实现二分法查找算法
以下是用C++实现二分法查找算法的示例代码:
```cpp
#include <iostream>
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int result = binarySearch(arr, 0, n - 1, target);
if (result == -1) {
std::cout << "Element not found" << std::endl;
} else {
std::cout << "Element found at index " << result << std::endl;
}
return 0;
}
```
c++编程实现顺序查找算法及二分法查找算法
以下是C++实现顺序查找算法和二分法查找算法的示例代码:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 顺序查找算法
int seqSearch(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == target) {
return i;
}
}
return -1; // 查找失败
}
// 二分法查找算法
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1; // 查找失败
}
int main() {
vector<int> nums = {3, 5, 2, 8, 4, 7, 1, 6};
sort(nums.begin(), nums.end()); // 二分法查找算法需要有序表
int target = 4;
int index1 = seqSearch(nums, target); // 调用顺序查找算法
int index2 = binarySearch(nums, target); // 调用二分法查找算法
if (index1 != -1) {
cout << "顺序查找成功,目标元素下标为:" << index1 << endl;
}
else {
cout << "顺序查找失败,未找到目标元素" << endl;
}
if (index2 != -1) {
cout << "二分法查找成功,目标元素下标为:" << index2 << endl;
}
else {
cout << "二分法查找失败,未找到目标元素" << endl;
}
return 0;
}
```
以上代码中,我们使用了STL中的vector容器来存储顺序表元素,并使用sort函数对其进行排序,以便二分法查找算法能够正确执行。在main函数中,我们分别调用了顺序查找算法和二分法查找算法,查找目标元素的值为4。最后,根据返回的下标值,输出查找结果。