帮我写一个二分法代码
时间: 2023-02-09 09:12:07 浏览: 106
二分法,又称折半查找,是一种在有序数组中查找某一特定元素的搜索算法。
下面是 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 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 6
result = binary_search(arr, x)
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in array")
上面的代码中,我们首先定义了一个名为 binary_search 的函数,它有两个参数:arr 和 x。在函数中,我们首先将最低下标设为 0,最高下标设为数组长度减 1。然后我们在 while 循环中执行查找。
在每次循环中,我们将中间下标设为(最高下标 + 最低下标)// 2。然后我们检查中间元素是否等于 x。如果等于 x,我们返回中间下标。
如果中间元素小于 x,我们将最低下标设为中间下标 + 1。
如果中间元素大于 x,我们将最高下标设为中间下标 - 1。
如果最低下标大于最高下标,我们返回 -1,表示找不到 x。
代码中返回-1,如果没有找到