python 实现二分查找

二分查找是利用了数组已经有序这一特性，在每次查找时先取数组的中间位置进行比对，根据比对结果可以确定查找范围是左半部分还是右半部分，然后递归地进行查找。以下是 Python 实现二分查找的代码：

def binary_search(nums, target):
    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

其中，nums 是已经有序的数组，target 是要查找的元素。如果查找成功，则返回该元素在数组中的下标；如果查找失败，则返回 -1。

相关问题

Python实现二分查找

二分查找又称折半查找，是一种在有序数组中查找给定值的算法。算法每次查找都将查找区间缩小一半，直到找到目标值或区间为空为止。

以下是Python实现二分查找的代码：

def binary_search(arr, target):
    left = 0  # 左指针
    right = len(arr) - 1  # 右指针
    while left <= right:
        mid = (left + right) // 2  # 中间位置
        if arr[mid] == target:
            return mid  # 找到目标值，返回下标
        elif arr[mid] > target:
            right = mid - 1  # 在左半边查找
        else:
            left = mid + 1  # 在右半边查找
    return -1  # 没有找到目标值，返回-1

该函数接受两个参数，一个有序数组和一个目标值。函数通过左右指针不断缩小查找区间，每次将中间位置与目标值比较，如果相等则返回中间位置，如果中间值大于目标值则在左半边继续查找，否则在右半边继续查找。如果查找完整个数组都没有找到目标值，则返回-1。

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。