C++给定一个已经按从小到大排列的整型数组data(data中没有重复元素),编写函数BinarySearch,用二分查找的方法判断data中是否存在元素key,若存在,输出key在data中的位置;否则,输出-1
时间: 2023-06-15 15:05:42 浏览: 44
以下是C++代码实现:
```cpp
#include <iostream>
using namespace std;
int BinarySearch(int data[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (data[mid] == key) {
return mid;
} else if (data[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(data) / sizeof(int);
int key = 5;
int index = BinarySearch(data, n, key);
if (index == -1) {
cout << "Not found." << endl;
} else {
cout << "Index of " << key << " is " << index << endl;
}
return 0;
}
```
BinarySearch函数接受三个参数:已经排好序的数组data,数组元素个数n,要查找的元素key。函数返回key在data中的位置(0-based),如果不存在则返回-1。
二分查找的核心思想是每次将查找区间缩小一半,直到找到目标元素或查找区间为空。在每一次迭代中,我们计算出查找区间的中间位置mid,比较data[mid]和key的大小,然后根据比较结果将查找区间缩小为左半部分或右半部分。如果最终查找区间为空,则key不存在于data中。