二分搜索算法python
时间: 2023-09-14 17:10:06 浏览: 48
下面是一个使用二分搜索算法在Python中查找有序列表中特定元素的示例代码:
```python
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
if result != -1:
print("元素在索引 %d" % result)
else:
print("元素不在数组中")
```
在上面的示例中,我们定义了一个名为 `binary_search` 的函数,它接受两个参数:一个有序数字列表和要搜索的元素 `x`。
在函数中,我们初始化 `low` 和 `high` 变量来表示要搜索的数字列表的范围。我们还创建一个 `mid` 变量来表示中间元素的索引。
在 while 循环中,我们首先计算中间元素的索引。如果这个中间元素小于我们要查找的元素 `x`,那么我们将 `low` 变量设置为 `mid + 1`,这样我们就可以继续在右边的子数组中查找。如果这个中间元素大于我们要查找的元素 `x`,那么我们将 `high` 变量设置为 `mid - 1`,这样我们就可以继续在左边的子数组中查找。如果这个中间元素正好是我们要查找的元素 `x`,我们就返回它的索引。
如果我们在 while 循环中没有找到要查找的元素,则返回 -1,表示该元素不在数字列表中。
在我们的示例中,我们创建了一个有序数字列表 `[2, 3, 4, 10, 40]`,并试图查找数字 `10` 的索引。由于数字 `10` 存在于该列表中,我们最终会打印出 `元素在索引 3`。如果我们尝试查找数字 `5` 的索引,我们会得到 `元素不在数组中` 的输出。