11.1 顺序查找与哨兵优化

顺序查找是最朴素的查找方法，就是从头到尾一个一个比对。虽然效率不高（时间复杂度O(n)），但胜在简单直接，不需要数据有序。

不过有个小技巧叫"哨兵优化"，能减少每次循环的边界检查。原理是在数组末尾临时放一个要找的目标值，这样循环时就不用每次都判断是否越界了。

下面看看具体怎么实现：

def sequential_search_with_sentinel(arr, target):
    """
    使用哨兵优化的顺序查找
    参数:
        arr: 待查找的列表
        target: 目标值
    返回:
        找到返回索引，没找到返回-1
    """
    # 保存原数组长度和最后一个元素
    n = len(arr)
    if n == 0:
        return -1
    
    last_element = arr[-1]  # 保存最后一个元素
    arr[-1] = target        # 设置哨兵
    
    i = 0
    # 循环直到找到目标值（因为有哨兵，一定能在数组内找到）
    while arr[i] != target:
        i += 1
    
    # 恢复最后一个元素
    arr[-1] = last_element
    
    # 如果在最后一个位置找到，需要确认是不是真正的目标
    if i < n - 1 or last_element == target:
        return i
    else:
        return -1

# 测试代码
try:
    test_arr = [3, 7, 2, 9, 1, 5]
    result = sequential_search_with_sentinel(test_arr.copy(), 9)
    print(f"查找9的结果: {result}")  # 应该输出3
    
    result = sequential_search_with_sentinel(test_arr.copy(), 8)
    print(f"查找8的结果: {result}")  # 应该输出-1
    
except Exception as e:
    print(f"查找过程中出现错误: {e}")

顺序查找实例方法表

功能名称	实例调用方法	具体功能、注意事项、参数说明
基础顺序查找	for i in range(len(arr)): if arr[i] == target: return i	最简单的实现，每次循环都要检查边界，时间复杂度O(n)，空间复杂度O(1)
哨兵优化查找	sequential_search_with_sentinel(arr, target)	减少边界检查次数，但需要修改原数组（所以通常传入副本），适用于频繁查找的场景

顺序查找虽然简单，但在某些特定场景下还是很有用的，比如数据量小或者数据无序的时候。哨兵优化这个小技巧体现了算法设计中"用空间换时间"的思想。

11.2 二分查找：循环不变式与边界控制

二分查找是查找算法中的明星选手，前提是数据必须有序。它的核心思想就是"猜中间，砍一半"，时间复杂度只有O(log n)，效率杠杠的。

不过二分查找看似简单，实际写起来很容易在边界条件上翻车。关键是要维护好"循环不变式"——也就是在整个循环过程中始终保持的某种状态。

最常见的有两种写法：左闭右闭区间[left, right]和左闭右开区间[left, right)。我们来看看左闭右闭的实现：

def binary_search(arr, target):
    """
    标准二分查找实现（左闭右闭区间）
    参数:
        arr: 已排序的列表（升序）
        target: 目标值
    返回:
        找到返回索引，没找到返回-1
    """
    left, right = 0, len(arr) - 1  # 初始化左右边界
    
    # 循环条件：left <= right，因为区间是左闭右闭
    while left <= right:
        mid = left + (right - left) // 2  # 防止整数溢出的写法
        
        if arr[mid] == target:
            return mid  # 找到了，返回索引
        elif arr[mid] < target:
            left = mid + 1  # 目标在右半部分
        else:
            right = mid - 1  # 目标在左半部分
    
    return -1  # 没找到

# 测试代码
try:
    sorted_arr = [1, 3, 5, 7, 9, 11, 13, 15]
    result = binary_search(sorted_arr, 7)
    print(f"查找7的结果: {result}")  # 应该输出3
    
    result = binary_search(sorted_arr, 8)
    print(f"查找8的结果: {result}")  # 应该输出-1
    
except Exception as e:
    print(f"二分查找过程中出现错误: {e}")

二分查找实例方法表

功能名称	实例调用方法	具体功能、注意事项、参数说明
标准二分查找	binary_search(arr, target)	要求输入数组已排序，返回第一个匹配的索引，时间复杂度O(log n)，空间复杂度O(1)
查找插入位置	bisect.bisect_left(arr, target)	Python内置模块，返回target应该插入的位置以保持有序

二分查找的关键在于理解循环不变式的含义：在每次循环开始时，如果目标存在，那么它一定在当前的搜索区间内。掌握这一点，边界条件就不会搞错了。

11.3 二分答案：在解空间中搜索

二分查找不仅能用来找数组中的元素，还能用来解决更复杂的问题——"二分答案"。这种思路特别巧妙：当我们要求解某个最优值时，可以先猜测一个答案，然后验证这个答案是否可行。

比如经典的"爱吃香蕉的珂珂"问题：给定若干堆香蕉和小时数H，求珂珂每小时最少吃多少根才能在H小时内吃完。这个问题的答案具有单调性——如果每小时吃K根能完成，那么吃K+1根也一定能完成。

def min_eating_speed(piles, h):
    """
    二分答案：求最小吃香蕉速度
    参数:
        piles: 香蕉堆列表，piles[i]表示第i堆的香蕉数量
        h: 可用小时数
    返回:
        最小吃香蕉速度（每小时根数）
    """
    def can_finish(speed):
        """验证给定速度是否能在h小时内吃完"""
        hours_needed = 0
        for pile in piles:
            # 向上取整：(pile + speed - 1) // speed
            hours_needed += (pile + speed - 1) // speed
        return hours_needed <= h
    
    # 答案的下界是1，上界是最大堆的香蕉数
    left, right = 1, max(piles)
    
    while left < right:
        mid = left + (right - left) // 2
        if can_finish(mid):
            right = mid  # 当前速度可行，尝试更小的速度
        else:
            left = mid + 1  # 当前速度不可行，需要更大的速度
    
    return left

# 测试代码
try:
    piles = [3, 6, 7, 11]
    h = 8
    result = min_eating_speed(piles, h)
    print(f"最小吃香蕉速度: {result}")  # 应该输出4
    
    piles = [30, 11, 23, 4, 20]
    h = 5
    result = min_eating_speed(piles, h)
    print(f"最小吃香蕉速度: {result}")  # 应该输出30
    
except Exception as e:
    print(f"二分答案过程中出现错误: {e}")

二分答案实例方法表

功能名称	实例调用方法	具体功能、注意事项、参数说明
最小化最大值	min_eating_speed(piles, h)	适用于"最小化最大消耗/时间/成本"类问题，需要定义验证函数
最大化最小值	类似框架，调整验证逻辑	适用于"最大化最小收益/距离/容量"类问题，同样需要验证函数

二分答案的核心是发现答案的单调性：如果某个答案可行，那么所有"更好"的答案都可行（或都不可行）。这种思路把优化问题转化为了判定问题，大大简化了思考过程。

11.4 旋转有序数组中的查找

旋转有序数组是个有趣的变种：原本有序的数组被从某个位置切开，前后两部分交换位置。比如[0,1,2,4,5,6,7]可能变成[4,5,6,7,0,1,2]。

在这种数组中查找目标值，不能直接用标准二分查找，但可以利用数组的部分有序性。关键观察是：无论怎么旋转，数组总有一半是有序的。

def search_rotated_array(nums, target):
    """
    在旋转有序数组中查找目标值
    参数:
        nums: 旋转后的有序数组（无重复元素）
        target: 目标值
    返回:
        找到返回索引，没找到返回-1
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        
        # 判断左半部分是否有序
        if nums[left] <= nums[mid]:
            # 左半部分有序
            if nums[left] <= target < nums[mid]:
                # 目标在左半部分
                right = mid - 1
            else:
                # 目标在右半部分
                left = mid + 1
        else:
            # 右半部分有序
            if nums[mid] < target <= nums[right]:
                # 目标在右半部分
                left = mid + 1
            else:
                # 目标在左半部分
                right = mid - 1
    
    return -1

# 测试代码
try:
    rotated_arr = [4, 5, 6, 7, 0, 1, 2]
    result = search_rotated_array(rotated_arr, 0)
    print(f"查找0的结果: {result}")  # 应该输出4
    
    result = search_rotated_array(rotated_arr, 3)
    print(f"查找3的结果: {result}")  # 应该输出-1
    
    # 边界情况：未旋转的数组
    normal_arr = [0, 1, 2, 4, 5, 6, 7]
    result = search_rotated_array(normal_arr, 4)
    print(f"查找4的结果: {result}")  # 应该输出3
    
except Exception as e:
    print(f"旋转数组查找过程中出现错误: {e}")

旋转数组查找实例方法表

功能名称	实例调用方法	具体功能、注意事项、参数说明
无重复旋转数组查找	search_rotated_array(nums, target)	数组中无重复元素，时间复杂度O(log n)，需要判断哪一半有序
有重复旋转数组查找	需要额外处理nums[left] == nums[mid]的情况	当存在重复元素时，最坏情况退化为O(n)，需要跳过重复元素

旋转有序数组的查找展示了二分查找的灵活性：即使数组不是完全有序的，只要存在某种规律性，就可能用二分的思想来解决。关键是要找到可以利用的有序部分。