给定一个已经按从小到大排列的整型数组data(data中没有重复元素),编写函数BinarySearch,用二分查找的方法判断data中是否存在元素key,若存在,输出key在data中的位置;否则,输出-1,给出该程序的c++代码
时间: 2024-05-16 07:14:17 浏览: 8
以下是C++代码实现:
```c++
int BinarySearch(int data[], int len, int key)
{
int left = 0, right = len - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (data[mid] == key)
return mid;
else if (data[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
```
其中,data是已经排好序的整型数组,len是数组的长度,key是需要查找的元素。程序使用了经典的二分查找算法,不断缩小查找范围,直到找到对应的元素或者确定该元素不存在。如果找到了对应的元素,函数返回该元素在数组中的位置;否则,返回-1。
相关问题
给定一个已经按从小到大排列的整型数组data(data中没有重复元素),编写函数BinarySearch,用二分查找的方法判断data中是否存在元素key,若存在,输出key在data中的位置;否则,输出-1
以下是使用Python实现的BinarySearch函数:
```python
def BinarySearch(data, key):
left, right = 0, len(data) - 1
while left <= right:
mid = (left + right) // 2
if data[mid] == key:
return mid
elif data[mid] < key:
left = mid + 1
else:
right = mid - 1
return -1
```
该函数的参数分别为已经按从小到大排列的整型数组data和要查找的元素key。函数中使用left和right两个变量分别表示数组的左右边界,初始值分别为0和len(data)-1。然后在while循环中,不断将中间位置mid与key进行比较,如果相等,则返回mid;如果mid小于key,则将left指向mid右侧的位置继续查找;如果mid大于key,则将right指向mid左侧的位置继续查找。如果最终没有找到key,则返回-1。
以下是一个例子,演示如何使用BinarySearch函数查找数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]中是否存在元素7:
```python
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
key = 7
index = BinarySearch(data, key)
if index != -1:
print("元素%d在数组中的位置为%d" % (key, index))
else:
print("元素%d不在数组中" % key)
```
输出结果为:元素7在数组中的位置为6。
C++给定一个已经按从小到大排列的整型数组data(data中没有重复元素),编写函数BinarySearch,用二分查找的方法判断data中是否存在元素key,若存在,输出key在data中的位置;否则,输出-1
以下是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中。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)