Python实现二分法查找(binary search)
对于从小到大有序排列的元素组合,使用二分法查找(binary search)是一种效率较高的算法,其大致流程如下:
- 将要查找的元素x与中间元素进行比较;
- 如果x与中间元素匹配,则返回中间元素的索引;
- 如果x大于中间元素,则取中间元素之后的部分,并使用这部分从第一步开始查找x;
- 如果x小于中间元素,则取中间元素之前的部分,并使用这部分从第一步开始查找x;
使用递归实现
def binary_search(arr, low, high, x):
if high < low: return -1
mid = (high + low) // 2
if arr[mid] == x:
# 找到元素返回中间索引
return mid
# If element is smaller than mid, then it can only
# be present in left subarray
elif arr[mid] > x:
# x < 中间元素,取中间元素左边的部分进行查找
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
#测试数据,必须是从小到大的有序元素
arr = [ 1 , 4 , 6 , 7 , 11 , 19 ]
x = 19
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print("元素的索引为:", str(result))
else:
print("没有找到元素!")
输出:
元素的索引为: 5
使用迭代的方式实现
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 , 4 , 6 , 7 , 11 , 19 ]
x = 19
result = binary_search(arr, x)
if result != -1:
print("元素的索引为:", str(result))
else:
print("没有找到元素!")