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 实现二分查找

### 回答1：

我可以为你提供一个Python实现二分查找的示例代码：def binary_search(array, target): n = len(array) left = 0 right = n - 1 while left <= right: mid = (left + right) // 2 if array[mid] == target: return mid elif array[mid] < target: left = mid + 1 else: right = mid - 1 return -1

### 回答2：
二分查找是一种高效的查找算法，可以用来在有序数组中快速找出特定元素的位置。下面是用Python实现二分查找的代码：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1

这段代码首先初始化了low和high两个变量，它们分别表示数组的起始和结束位置。然后，利用一个while循环来在数组中查找目标元素。

在循环中，首先计算出当前的中间位置mid。然后，判断mid位置的元素与目标元素的大小关系。

- 如果mid位置的元素等于目标元素，说明找到了目标，直接返回mid。
- 如果mid位置的元素小于目标元素，说明目标元素在mid右侧，将low更新为mid+1。
- 如果mid位置的元素大于目标元素，说明目标元素在mid左侧，将high更新为mid-1。

如果循环结束后仍然没有找到目标元素，说明目标元素不存在于数组中，返回-1。

这就是用Python实现二分查找的基本过程。二分查找的时间复杂度为O(log n)，比线性查找更加高效。

### 回答3：
二分查找（Binary Search）是一种高效的搜索算法，用于在有序数组中查找目标元素。以下是使用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:
            left = mid + 1
        else:
            right = mid - 1

    return -1

arr = [2, 4, 6, 8, 10, 12, 14, 16]
target = 10
result = binary_search(arr, target)

if result != -1:
    print("目标元素在数组中的索引为:", result)
else:
    print("目标元素不在数组中")

以上代码实现了`binary_search`函数，该函数接受一个有序数组`arr`和目标元素`target`作为输入，返回目标元素在数组中的索引。若目标元素不在数组中，则返回-1。函数内部使用`left`和`right`两个指针来确定每次查找的区间范围，通过不断缩小区间来逐步逼近目标元素。最后，根据返回的结果判断目标元素是否在数组中，并输出相应结果。

在以上示例中，`arr`为有序数组`[2, 4, 6, 8, 10, 12, 14, 16]`，`target`为10。根据二分查找算法，函数返回的结果为4，即10在数组中的索引位置。最后，输出结果为"目标元素在数组中的索引为: 4"。

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。