二分查找算法详解

二分查找算法详解

二分查找算法(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。