二分查找 - 算法入门

← 返回课程算法入门 › 第 6 关

进度 0%

第 6 关：二分查找

Python/C++进阶

📖 本课目标

本关属于《算法入门》第 6 课。阅读右侧代码模板，理解每一行的作用，然后动手修改并完成练习。

🎯 本课要点

二分查找

🛠 学习方式

阅读右侧代码模板中的注释与实现
修改代码，尝试达成新的效果
点击「运行」查看实际输出
确认理解后点击「提交」标记本关完成

💡 说明

本关为 Python/C++，浏览器内无法真正执行该语言。当前「运行」输出为演示结果，请在本地环境中编译运行以验证代码。

main.pytest.py

# 二分查找

def binary_search(arr, target):
    """标准二分查找"""
    left, right = 0, len(arr) - 1
    steps = 0
    
    while left <= right:
        steps += 1
        mid = (left + right) // 2
        
        if arr[mid] == target:
            print(f"  找到 {target}！索引: {mid}，用了 {steps} 步")
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    print(f"  未找到 {target}，用了 {steps} 步")
    return -1

# 测试
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(f"数组: {data}\n")
binary_search(data, 23)
binary_search(data, 56)
binary_search(data, 10)

# 查找范围的二分
def search_range(arr, target):
    """查找目标值的起始和结束位置"""
    def find_first(arr, target):
        left, right = 0, len(arr) - 1
        result = -1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] >= target:
                if arr[mid] == target:
                    result = mid
                right = mid - 1
            else:
                left = mid + 1
        return result
    
    def find_last(arr, target):
        left, right = 0, len(arr) - 1
        result = -1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] <= target:
                if arr[mid] == target:
                    result = mid
                left = mid + 1
            else:
                right = mid - 1
        return result
    
    return find_first(arr, target), find_last(arr, target)

data2 = [1, 2, 2, 2, 3, 4, 5]
print(f"\n数组: {data2}")
first, last = search_range(data2, 2)
print(f"  2 的范围: [{first}, {last}]")

# 效率对比
import time
big_data = list(range(0, 1000000, 2))
print(f"\n在 {len(big_data)} 个元素中查找:")
binary_search(big_data, 999998)

点击「运行」或「提交代码」查看结果

📖 查看本课说明

第 6 关：二分查找

Python/C++ · 进阶 · 《算法入门》

二分查找

本关为 Python/C++，浏览器无法真正编译运行，请在本地环境验证代码。