写出一个程序代码(1)掌握折半查找算法的思想及程序实现。
时间: 2024-03-24 18:38:51 浏览: 21
好的,以下是一个使用折半查找算法的 Python 代码示例:
```python
def binary_search(arr, x):
"""
在有序数组 arr 中查找元素 x 的索引,如果不存在则返回 -1
"""
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
```
该函数接收一个有序数组和要查找的元素作为参数,然后使用二分法在数组中查找该元素。如果找到了,返回该元素在数组中的索引;如果未找到,则返回 -1。
相关问题
写出一个程序(1)掌握折半查找算法的思想及程序实现。
好的,以下是一个使用折半查找算法的 C++ 代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
int binary_search(vector<int>& arr, int x) {
/*
* 在有序数组 arr 中查找元素 x 的索引,如果不存在则返回 -1
*/
int low = 0, high = arr.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] < x) {
low = mid + 1;
} else if (arr[mid] > x) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
int x = 9;
int idx = binary_search(arr, x);
if (idx == -1) {
cout << "Element not found." << endl;
} else {
cout << "Element found at index " << idx << endl;
}
return 0;
}
```
该程序定义了一个 `binary_search` 函数,该函数接收一个有序数组和要查找的元素作为参数,然后使用二分法在数组中查找该元素。如果找到了,返回该元素在数组中的索引;如果未找到,则返回 -1。`main` 函数则定义了一个示例数组和要查找的元素,并调用 `binary_search` 函数进行查找,最后输出查找结果。
写一个代码,实现折半查找算法
好的,以下是 Python 代码实现折半查找算法:
```python
def binarySearch(arr, target):
"""
在有序数组 arr 中查找元素 target,返回其下标,若不存在则返回 -1
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
其中,arr 表示有序数组,target 表示待查找元素。该函数通过不断缩小查找范围,最终找到目标元素或者判断其不存在,返回相应的下标或 -1。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)