这个是怎么搞的我不明白

Question

用二分查找实现下列序列的查找{3,6,9,16,21,29,56,67,89,99}

Answer 1

引自免费微信小程序：皆我百晓生

当然可以，让我们一步一步地理解如何使用二分查找算法在给定的有序序列中查找特定数值。

二分查找算法适用于已排序的列表。它的基本思想是将列表分成两半，然后比较要查找的值与中间元素的值。如果要查找的值小于中间元素，就在左半部分继续查找；如果要查找的值大于中间元素，则在右半部分查找。重复这个过程，直到找到目标值，或者搜索范围为空（表示未找到）。

以下是使用Python实现二分查找的步骤和代码：

步骤：

1. 初始化两个指针，left 和 right，分别指向序列的开始和结束。
2. 计算中间索引 mid，即 (left + right) // 2。
3. 检查中间元素是否等于要查找的目标值：
   • 如果相等，返回中间元素的索引。
   • 如果目标值小于中间元素，更新 right = mid - 1，并重新从步骤2开始。
   • 如果目标值大于中间元素，更新 left = mid + 1，并重新从步骤2开始。
4. 当 left > right 时，表示没有找到目标值，返回一个特殊值（例如 -1）表示找不到。

代码：

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

# 测试序列
sequence = [3, 6, 9, 16, 21, 29, 56, 67, 89, 99]

# 查找数字 21 的索引
target = 21
index = binary_search(sequence, target)

if index != -1:
    print(f"找到了，数字 {target} 在序列中的索引为 {index}")
else:
    print("未找到数字")

这段代码首先定义了一个名为 binary_search 的函数，它接受一个排序好的数组 arr 和一个要查找的目标值 target。然后我们初始化了两个指针 left 和 right，并进入循环。在每次迭代中，我们都计算中间索引，并根据中间元素与目标值的关系调整搜索范围。当找到目标值时，函数返回其索引；如果没有找到，返回 -1。

对于测试序列 [3, 6, 9, 16, 21, 29, 56, 67, 89, 99] 和目标值 21，运行这段代码将会输出 "找到了，数字 21 在序列中的索引为 4"。