7-2 二分查找改写
时间: 2023-11-11 13:56:02 浏览: 111
二分查找是一种在有序数组中查找目标元素的算法。该算法通过将目标元素与数组中间元素进行比较,并根据比较结果决定继续在左半部分或右半部分继续查找,以此类推,直到找到目标元素或确定目标元素不存在。
对于给出的问题,要将7-2的二分查找进行改写,可以按照以下步骤进行:
1. 初始化low指针指向数组的第一个元素,high指针指向数组的最后一个元素。
2. 计算middle指针的位置,即 (low + high) / 2。
3. 比较middle指针的元素与目标元素的大小关系:
a. 如果目标元素等于middle指针的元素,则返回middle。
b. 如果目标元素小于middle指针的元素,则将high指针更新为middle - 1,继续在左半部分查找。
c. 如果目标元素大于middle指针的元素,则将low指针更新为middle + 1,继续在右半部分查找。
4. 重复步骤2和步骤3,直到low指针大于high指针,表示目标元素不存在于数组中。
改写后的二分查找代码如下:
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
middle = (low + high) // 2
if arr[middle] == target:
return middle
elif arr[middle] > target:
high = middle - 1
else:
low = middle + 1
return -1
```