Python写的二分查找
时间: 2023-05-31 09:05:37 浏览: 54
以下是Python写的二分查找的代码:
```
def binary_search(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
# 测试
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
if result != -1:
print("元素在索引 %d" % result)
else:
print("元素不在数组中")
```
该函数接受一个已排序的数组 `arr` 和要查找的元素 `x`,返回 `x` 在数组中的索引值,如果 `x` 不在数组中,返回 -1。
在函数中,我们使用两个变量 `left` 和 `right` 分别表示数组的左右边界,初始时 `left` 为 0,`right` 为数组的长度减 1。然后,我们进入一个循环,每次将 `mid` 设为 `left` 和 `right` 的中间位置,如果 `arr[mid]` 等于 `x`,则直接返回 `mid`。如果 `arr[mid]` 小于 `x`,则说明 `x` 在 `mid` 的右侧,更新 `left` 为 `mid + 1`。如果 `arr[mid]` 大于 `x`,则说明 `x` 在 `mid` 的左侧,更新 `right` 为 `mid - 1`。当 `left` 大于 `right` 时,说明 `x` 不在数组中,返回 -1。
在上述代码中,我们还添加了一个测试函数,用于测试二分查找的正确性。我们定义了一个数组 `arr`,包含元素 2、3、4、10 和 40,然后查找元素 `x` 是否在数组中,如果在,返回元素的索引值,否则返回 -1。在本例中,元素 `x` 为 10,在数组中的索引为 3,因此该函数应该返回 3。