二分查找法python代码
时间: 2023-10-14 09:28:34 浏览: 82
以下是二分查找法的Python代码:
```python
def binary_search(alist, item):
first = 0
last = len(alist)-1
found = False
while first<=last and not found:
midpoint = (first + last)//2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return found
```
注意:以上代码仅供参考,实际使用时可能需要根据具体情况进行修改。
相关问题
python 二分查找法
二分查找法是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成两部分,然后判断目标值在哪一部分中,从而缩小搜索范围。
下面是一个用 Python 实现的二分查找法的示例代码:
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # 目标值不存在
# 示例使用
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
result = binary_search(arr, target)
if result != -1:
print(f"目标值 {target} 在数组中的索引为 {result}")
else:
print(f"目标值 {target} 不在数组中")
```
在这个示例中,我们定义了一个 `binary_search` 函数,接受一个有序数组 `arr` 和目标值 `target` 作为参数。我们使用两个指针 `low` 和 `high` 来表示当前搜索范围的左右边界。在每次循环中,我们计算中间位置 `mid`,然后比较 `arr[mid]` 和 `target` 的大小关系来决定下一步搜索的范围。
如果 `arr[mid]` 等于 `target`,则找到目标值,返回 `mid`。如果 `arr[mid]` 小于 `target`,则说明目标值在 `mid` 的右侧,更新 `low` 为 `mid + 1`。如果 `arr[mid]` 大于 `target`,则说明目标值在 `mid` 的左侧,更新 `high` 为 `mid - 1`。
如果循环结束后仍然没有找到目标值,则返回 -1 表示目标值不存在于数组中。
使用示例中的数组和目标值,程序会输出 "目标值 6 在数组中的索引为 5"。
写出二分查找法的代码
二分查找法,也称为折半查找,是一种在有序数组中查找特定元素的搜索算法。它的工作原理是每次比较中间元素与目标值,然后根据比较结果缩小搜索范围,直到找到目标或确定目标不存在。以下是一个简单的 Python 代码实现:
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # 如果未找到,返回 -1 表示目标不在数组中
# 使用方法
arr = [1, 3, 5, 7, 9] # 假设这是一个有序列表
target = 5
result = binary_search(arr, target)
if result != -1:
print(f"元素 {target} 在数组中的索引为 {result}")
else:
print(f"元素 {target} 不在数组中")
```
阅读全文