用Python写一个二分查找
时间: 2023-08-31 19:36:31 浏览: 168
### 回答1:
二分查找是一种在有序列表中查找某一特定元素的搜索算法。下面是一个 Python 代码示例:
```
def binary_search(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
guess = list[mid]
if guess == item:
return mid
elif guess > item:
high = mid - 1
else:
low = mid + 1
return None
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # Output: 1
print(binary_search(my_list, -1)) # Output: None
```
该代码定义了一个名为 `binary_search` 的函数,它接收一个有序列表和要查找的元素作为参数。函数使用一个循环来查找元素,每次将列表的中间元素与要查找的元素进行比较。如果找到了该元素,则返回它在列表中的索引。否则,如果中间元素大于要查找的元素,则在列表的左半部分继续查找;如果中间元素小于要查找的元素,则在列表的右半部分继续查找。如果列表中没有该元素,则返回 `None`。
### 回答2:
二分查找是一种在已排序的数组中查找目标元素的算法。它的基本思想是将目标元素与数组的中间元素进行比较,如果相等则返回该位置,如果目标元素小于中间元素,则继续在左半部分查找,否则在右半部分查找,直到找到目标元素或者找不到为止。
下面是用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`是一个已排序的数组,`target`是要查找的目标元素。在每次循环中,通过计算中间位置`mid`来进行比较,如果相等则返回`mid`,如果目标元素小于中间元素,则缩小查找范围到左半部分,否则缩小到右半部分。如果最终找不到目标元素,则返回`-1`。
使用上述代码可以进行二分查找,例如:
```python
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 6
result = binary_search(arr, target)
if result != -1:
print(f"目标元素在数组中的位置是:{result}")
else:
print("目标元素不在数组中")
```
以上代码会输出目标元素在数组中的位置是:5,表示目标元素6在数组的第6个位置。
### 回答3:
二分查找算法是一种在有序数组中查找特定元素的搜索算法。它通过将数组分成两部分来进行查找,然后判断目标值是否在中间元素的左边或右边,从而缩小查找范围。下面给出一个使用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
```
在这个算法中,我们首先设定数组的起始位置`low`为0,终止位置`high`为数组长度减1。然后,我们通过将`low`和`high`的中间位置`mid`计算出来。将`mid`位置的元素与目标值进行比较,如果相等则返回`mid`,如果`mid`位置的元素小于目标值,则说明目标值可能在中间元素的右边,此时将`low`更新为`mid + 1`,否则将`high`更新为`mid - 1`。在每一次迭代中,我们通过调整`low`和`high`的值不断缩小查找范围,直到找到目标值或查找范围为空(`low`大于`high`)为止。
以上是一个基本的二分查找算法示例,可以通过传入一个有序数组和目标值来进行查找。如果目标值存在于数组中,则返回其索引值;否则返回-1,表示未找到。
阅读全文