使用python编写折半查找算法,算法描述如下: (1) 将数组或列表有序排列。 (2) 设置左指针 left = 0,右指针 right = len(array) - 1。 (3) 计算中间指针 mid = (left + right) // 2。 (4) 如果中间指针所指元素等于目标值,则返回 mid。 (5) 如果中间指针所指元素大于目标值,则在左半区间继续搜索,right = mid - 1。 (6) 如果中间指针所指元素小于目标值,则在右半区间继续搜索,left = mid + 1。 (7) 重复步骤 3-6,直到找到目标元素或区间为空。 (8) 如果区间为空也未找到目标值,则返回 -1。
时间: 2024-03-04 19:49:13 浏览: 20
以下是使用Python编写的折半查找算法:
```python
def binary_search(array, target):
"""
在有序数组array中查找目标元素target,返回其下标。
如果未找到则返回-1。
"""
left, right = 0, len(array) - 1
while left <= right:
mid = (left + right) // 2 # 计算中间位置
if array[mid] == target:
return mid # 找到目标元素,返回下标
elif array[mid] > target:
right = mid - 1 # 目标元素在左半区间
else:
left = mid + 1 # 目标元素在右半区间
return -1 # 未找到目标元素,返回-1
```
函数接受一个有序数组array和一个目标元素target作为参数。函数首先将左指针left设为0,右指针right设为数组长度减1。然后,在每次循环中计算中间位置mid,如果array[mid]等于目标元素target,则返回mid;如果array[mid]大于target,则说明目标元素在左半区间,将右指针right设为mid-1;如果array[mid]小于target,则说明目标元素在右半区间,将左指针left设为mid+1。如果循环结束后仍未找到目标元素,则返回-1。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)