python实现二分查找

二分查找是一种基于比较目标值和数组中间元素大小的查找算法，其时间复杂度为O(logn)。下面是Python实现二分查找的代码。

def binary_search(nums, target):
    """
    二分查找
    :param nums: 有序数组
    :param target: 目标值
    :return: 目标值在数组中的索引，如果不存在则返回-1
    """
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

在实现中，我们使用两个指针left和right分别指向数组的左右两端，然后用mid来表示数组的中间位置。每次比较目标值和mid的大小关系，如果相等则返回mid的索引，如果目标值大于mid，则将left指针移动到mid+1的位置，否则将right指针移动到mid-1的位置。如果left>right，则说明目标值不存在于数组中，返回-1。