二分查找算法(Binary Search Algorithm)也称为折半查找算法,是一种针对有序数组的查找算法。它的原理是:首先确定待查找区间的中间位置,然后将待查找元素与中间位置的元素进行比较。如果待查找元素等于中间位置的元素,则查找成功;如果待查找元素小于中间位置的元素,则在左半部分继续查找;如果待查找元素大于中间位置的元素,则在右半部分继续查找。不断重复这个过程,直到找到待查找元素或者确定待查找区间为空,此时查找失败。
二分查找算法的时间复杂度为O(log n),比顺序查找算法的时间复杂度O(n)更加高效。但是,二分查找算法的前提是数组必须是有序的,如果数组无序,则需要先进行排序,这将增加时间复杂度。
下面是二分查找算法的Python实现代码:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
其中,arr为有序数组,target为待查找元素。函数返回待查找元素在数组中的索引,如果不存在则返回-1。