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:
            left = mid + 1
        else:
            right = mid - 1
    return -1

其中，`arr`是待查找的有序数组，`target`是要查找的目标元素。函数返回目标元素在数组中的索引，如果目标元素不在数组中，则返回-1。

相关问题

用Python写二分查找算法

### 回答1：
二分查找算法是一种常见的查找算法，可以在有序的数组或列表中快速查找目标元素。以下是使用Python实现的二分查找算法：

def binary_search(arr, target):
    """
    在有序数组arr中查找目标元素target，返回其索引位置，如果未找到，则返回-1。
    """
    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

该函数接受两个参数，一个有序的数组和一个目标元素。在算法执行期间，首先定义左右指针，然后在数组中循环，每次找到数组的中间位置。如果中间元素是目标元素，则返回其索引。否则，如果中间元素小于目标元素，则说明目标元素在中间元素的右侧，因此将左指针设置为mid + 1。如果中间元素大于目标元素，则说明目标元素在中间元素的左侧，因此将右指针设置为mid - 1。如果最终未找到目标元素，则返回-1。

### 回答2：
二分查找算法是一种高效的搜索算法，它可以在有序数组中快速定位目标元素的位置。下面是用Python编写的二分查找算法：

def binary_search(arr, target):
    low, high = 0, 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`指向数组的最后一个元素。然后我们通过计算中间元素的索引来实现二分查找。

在每一轮循环中，我们首先判断中间元素是否等于目标元素。如果是，则返回中间元素的索引。如果不是，我们根据中间元素和目标元素的大小关系来调整 `low`和`high`的值。

如果中间元素小于目标元素，则说明目标元素可能在中间元素的右侧，我们将 `low`指向中间元素的下一个位置。如果中间元素大于目标元素，则说明目标元素可能在中间元素的左侧，我们将 `high`指向中间元素的上一个位置。

通过不断地二分查找，直到找到目标元素或者`low`大于`high`，即整个数组被遍历完毕时，如果没有找到目标元素，则返回-1。

以上就是使用Python编写的二分查找算法。这个算法的时间复杂度为O(log n)，其中`n`是数组的大小。

### 回答3：
二分查找算法是一种高效的搜索算法，可以在有序数组中查找指定元素的位置。

以下是使用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

# 测试示例
array = [2, 4, 6, 8, 10, 12, 14]
target = 10
result = binary_search(array, target)

if result != -1:
    print("元素在数组中的位置为:", result)
else:
    print("元素不在数组中")

以上代码中，`binary_search`函数将有序数组`arr`和目标元素`target`作为输入参数。通过将搜索范围的左右边界不断逼近，直到找到目标元素或搜索范围为空时循环结束。

在每次循环中，计算中间位置`mid`，并与目标元素进行比较。如果`arr[mid]`等于目标元素`target`，则返回`mid`；如果`arr[mid]`小于`target`，则目标元素在中间位置的右侧，更新左边界`left`为`mid + 1`；如果`arr[mid]`大于`target`，则目标元素在中间位置的左侧，更新右边界`right`为`mid - 1`。

最后，如果循环结束时仍未找到目标元素，则返回-1表示目标元素不在数组中。

在示例代码中，数组`[2, 4, 6, 8, 10, 12, 14]`中查找目标元素`10`，返回的结果为`4`，表示目标元素在数组中的位置为索引`4`。

编写递归函数，实现二分查找问题。

二分查找是一种在有序数组中查找特定元素的算法，它通过反复将搜索范围缩小一半来提高效率。在编写递归版本的二分查找时，我们可以按照以下步骤：

1. 定义基本情况：如果数组为空或者只有一个元素，直接返回数组索引（若目标值等于第一个元素则返回0，否则返回-1）。

2. 递归条件：假设数组有n个元素，我们将数组分为两部分，中间位置的索引称为mid。然后我们比较目标值（target）与中间元素：
- 如果 target 小于中间元素，则在左半部分的子数组中继续查找，调用递归函数并传入left（开始索引）和 mid-1；
- 如果 target 大于中间元素，则在右半部分的子数组中查找，调用递归函数并传入mid+1和 right（结束索引）；
- 如果 target 等于中间元素，找到了目标，返回 mid。

递归函数的伪代码示例（Python风格）：

def binary_search(arr, low, high, target):
    if low > high:  # 边界情况：数组为空或只有一个元素
        return -1
    mid = (low + high) // 2

    if arr[mid] == target:  # 目标在中间
        return mid
    elif arr[mid] < target:  # 需要在右半部分查找
        return binary_search(arr, mid + 1, high, target)
    else:  # 需要在左半部分查找
        return binary_search(arr, low, mid - 1, target)