二分搜索python
时间: 2023-11-15 16:02:32 浏览: 46
二分搜索(Binary Search)是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成两个部分,判断目标元素在哪个部分,然后继续在该部分中进行查找,直到找到目标元素或者确定目标元素不存在为止。在Python中,可以使用递归或者循环的方式实现二分搜索算法。
以下是使用Python实现二分查找算法的核心代码:
引用:
```
def binary_search(arr, target):
left = 0
right = 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`表示要查找的目标元素。首先,定义左右两个指针`left`和`right`,分别指向数组的第一个元素和最后一个元素。然后,使用循环不断缩小查找范围,直到找到目标元素或者确定目标元素不存在为止。在每次循环中,计算中间位置`mid`,并判断目标元素在左半部分还是右半部分。如果目标元素等于中间位置的元素,则直接返回中间位置的索引;如果目标元素小于中间位置的元素,则在左半部分继续查找;如果目标元素大于中间位置的元素,则在右半部分继续查找。如果最终没有找到目标元素,则返回-1。
除了循环实现外,还可以使用递归的方式实现二分搜索算法。以下是使用Python实现二分查找算法的递归代码:
引用:
```
class BinarySearch(object):
def binary_search(self, array, data):
"""二分查找法递归实现"""
if len(array) == 0:
return False
array.sort()
mid_index = len(array) // 2
if array[mid_index] == data:
return True
return self.binary_search(array[mid_index + 1:], data) if data > array[mid_index] else \
self.binary_search(array[:mid_index], data)
```
上述代码中,`array`表示有序数组,`data`表示要查找的目标元素。首先,判断数组是否为空,如果为空则返回False。然后,对数组进行排序,以便进行二分查找。接着,计算中间位置`mid_index`,并判断目标元素在左半部分还是右半部分。如果目标元素等于中间位置的元素,则直接返回True;如果目标元素小于中间位置的元素,则在左半部分继续查找;如果目标元素大于中间位置的元素,则在右半部分继续查找。如果最终没有找到目标元素,则返回False。