用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-10 13:50:12 浏览: 21
好的,以下是Python实现折半查找算法的代码:
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1 # 设置左右指针
while left <= right:
mid = (left + right) // 2 # 计算中间指针
if arr[mid] == target: # 如果中间指针所指元素等于目标值,则返回mid
return mid
elif arr[mid] > target: # 如果中间指针所指元素大于目标值,则在左半区间继续搜索
right = mid - 1
else: # 如果中间指针所指元素小于目标值,则在右半区间继续搜索
left = mid + 1
return -1 # 如果区间为空也未找到目标值,则返回-1
# 测试代码
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
print(binary_search(arr, target)) # 输出 5
```
这段代码使用了循环的方式实现折半查找算法。首先设置左右指针,然后计算中间指针。如果中间指针所指元素等于目标值,则返回中间指针;如果中间指针所指元素大于目标值,则在左半区间继续搜索,将右指针向中间指针左边移动一位;如果中间指针所指元素小于目标值,则在右半区间继续搜索,将左指针向中间指针右边移动一位。然后重复以上步骤,直到找到目标元素或区间为空。如果区间为空也未找到目标值,则返回-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_column_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)