python二分法查找
时间: 2023-06-29 15:15:15 浏览: 69
二分查找是一种在有序数组中查找特定元素的搜索算法。算法的工作原理是将数组分成两个部分:已排序的一部分和未排序的一部分,然后确定要查找的元素在哪个部分中,进而继续在该部分中进行查找,直到找到该元素或确定该元素不存在为止。
以下是 Python 实现二分查找的代码示例:
```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:
left = mid + 1
else:
right = mid - 1
return -1
```
其中,参数 `arr` 表示要搜索的有序数组,`target` 表示要查找的目标元素,函数返回目标元素在数组中的索引值,如果目标元素不存在则返回 `-1`。
相关问题
python 二分法查找算法
二分法查找算法也被称为折半查找算法,它是一种高效的查找算法。它的基本思想是:将有序数组分成两部分,取数组中间的元素与目标值进行比较,如果中间元素等于目标值,则直接返回;如果中间元素大于目标值,则在左半部分继续查找;如果中间元素小于目标值,则在右半部分继续查找。重复上述过程,直到数组中不存在目标值,或者查找范围为空。
以下是 Python 实现二分法查找算法的代码:
```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:
left = mid + 1
else:
right = mid - 1
return -1
```
其中,`arr` 为有序数组,`target` 为目标值。函数返回目标值在数组中的下标,如果不存在则返回 -1。
使用示例:
```python
arr = [1, 3, 5, 7, 9]
target = 5
print(binary_search(arr, target)) # 输出:2
```
时间复杂度为 O(logn),比线性查找算法要快得多。
python 二分法查找的精髓
Python中的二法查找是一种高效的查找算法,它通过将查找范围逐渐缩小一半来快速定位目标元素。以下是二分法查找的精髓:
1. 确定查找范围:首先需要确定查找的起始位置和结束位置。通常情况下,起始位置为数组的第一个元素,结束位置为数组的最后一个元素。
2. 计算中间位置:通过计算起始位置和结束位置的中间位置,可以得到当前查找范围的中间元素。
3. 比较目标值:将目标值与中间元素进行比较。如果目标值等于中间元素,则查找成功;如果目标值小于中间元素,则在左半部分继续查找;如果目标值大于中间元素,则在右半部分继续查找。
4. 更新查找范围:根据比较结果更新查找范围。如果目标值小于中间元素,则将结束位置更新为中间位置减1;如果目标值大于中间元素,则将起始位置更新为中间位置加1。
5. 重复以上步骤:不断重复以上步骤,直到找到目标元素或者查找范围为空。
二分法查找的时间复杂度为O(log n),其中n为数组的长度。这是因为每次查找都将查找范围缩小一半,所以最多需要进行log n次比较。