binary search python
时间: 2023-04-26 17:01:10 浏览: 105
二分查找是一种高效的查找算法,它可以在有序数组中快速定位目标元素。在 Python 中,可以使用递归或循环实现二分查找。具体实现方式可以参考以下代码:
递归实现:
```python
def binary_search(arr, target):
if not arr:
return -1
mid = len(arr) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr[:mid], target)
else:
res = binary_search(arr[mid+1:], target)
return res + mid + 1 if res != -1 else -1
```
循环实现:
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1
```
以上代码中,arr 表示有序数组,target 表示目标元素。递归实现中,每次将数组分成两部分,判断目标元素在哪一部分,然后递归查找。循环实现中,使用两个指针 left 和 right 分别指向数组的左右两端,每次将中间位置 mid 与目标元素比较,然后根据比较结果更新左右指针的位置。如果最终没有找到目标元素,则返回 -1。
阅读全文