在一个给定的n个元素的有序序列中查找出与给定关键字x相同的元素的具体位置。即输入一个n个元素的序列,其中n个元素从小到大的顺序排列,查找是否存在给定的值x.(用二分查找法)。请用c++代码实现
时间: 2024-09-11 19:05:27 浏览: 45
给定N个不同的整数,要求对这N个整数按如下规则排序并输出
5星 · 资源好评率100%
二分查找法是一种高效的查找算法,它适用于有序数组。在二分查找中,我们首先确定数组的中间位置,然后比较中间元素与目标值。如果它们相等,则找到目标值。如果目标值小于中间元素,则在左半部分继续查找;如果目标值大于中间元素,则在右半部分继续查找。这个过程一直重复,直到找到目标值或者子数组为空。
以下是使用C++实现的二分查找算法代码:
```cpp
#include <iostream>
using namespace std;
// 二分查找函数
int binarySearch(int arr[], int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
// 检查x是否在中间位置
if (arr[m] == x) {
return m; // 返回索引
}
// 如果x大于中间位置的值,则只在右半边搜索
if (arr[m] < x) {
l = m + 1;
}
// 如果x小于中间位置的值,则只在左半边搜索
else {
r = m - 1;
}
}
// 如果元素不存在返回 -1
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40}; // 给定的有序数组
int n = sizeof(arr) / sizeof(arr[0]); // 数组中的元素数量
int x = 10; // 给定的关键字
int result = binarySearch(arr, 0, n - 1, x); // 调用二分查找函数
if (result == -1) {
cout << "元素在数组中不存在" << endl;
} else {
cout << "元素在数组中的索引位置为: " << result << endl;
}
return 0;
}
```
阅读全文