查找算法

1. 查找算法概述

查找（Search）是计算机科学中最基本的操作之一——在数据集合中寻找满足特定条件的元素。根据数据是否有序、存储结构不同，查找算法的选择也各不相同。

1.1 查找算法分类

2. 顺序查找

2.1 基本实现

顺序查找（Sequential Search）从数据集合的第一个元素开始，逐个比较，直到找到目标或遍历完毕。

// Java：顺序查找
public int sequentialSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1; // 未找到
}

# Python：顺序查找
def sequential_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

2.2 哨兵优化

在数组末尾放置哨兵，避免每次循环都检查边界：

// Java：带哨兵的顺序查找
public int sentinelSearch(int[] arr, int target) {
    int n = arr.length;
    int last = arr[n - 1];  // 保存末尾元素
    arr[n - 1] = target;    // 设置哨兵

    int i = 0;
    while (arr[i] != target) {
        i++;
    }

    arr[n - 1] = last;      // 恢复末尾元素
    if (i < n - 1 || last == target) {
        return i;
    }
    return -1;
}

2.3 复杂度分析

顺序查找适用于无序数据或链表等不支持随机访问的结构。对于有序数据，二分查找是更优选择。

3. 二分查找

3.1 二分查找原理

二分查找（Binary Search）要求数据有序且支持随机访问。每次将查找区间缩小一半：

在 [1, 3, 5, 7, 9, 11, 13, 15] 中查找 7：

第1轮: [1, 3, 5, 7, 9, 11, 13, 15]  mid=4, arr[4]=9 > 7 → 左半
第2轮: [1, 3, 5, 7]                  mid=1, arr[1]=3 < 7 → 右半
第3轮: [5, 7]                        mid=2, arr[2]=5 < 7 → 右半
第4轮: [7]                           mid=3, arr[3]=7 = 7 → 找到!

3.2 标准二分查找

// Java：标准二分查找（查找目标值，返回索引）
public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 未找到
}

# Python：标准二分查找
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    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

// C++：标准二分查找
int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

3.3 防止整数溢出

计算中点时，(left + right) / 2 在 left + right 超过 int 最大值时会溢出：

//  可能溢出
int mid = (left + right) / 2;

//  安全写法
int mid = left + (right - left) / 2;

//  无符号右移（Java）
int mid = (left + right) >>> 1;

3.4 复杂度分析

二分查找每次将搜索空间减半，n 个元素最多比较 ⌊log₂n⌋ + 1 次：

4. 二分查找变体

4.1 查找第一个等于目标的位置

当数组中有重复元素时，找到目标值第一次出现的位置：

// Java：查找第一个等于 target 的位置
public int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid; // arr[mid] >= target 时，右边界收缩
        }
    }
    return left; // left 是第一个 >= target 的位置
}

# Python：bisect 模块提供现成实现
import bisect

arr = [1, 2, 2, 2, 3, 4, 5]
target = 2

# 第一个 >= target 的位置
pos = bisect.bisect_left(arr, target)  # 1

# 第一个 > target 的位置
pos = bisect.bisect_right(arr, target) # 4

4.2 查找最后一个等于目标的位置

// Java：查找最后一个等于 target 的位置
public int upperBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid; // arr[mid] > target 时，右边界收缩
        }
    }
    return left - 1; // left - 1 是最后一个 <= target 的位置
}

4.3 查找插入位置

在有序数组中找到目标值应该插入的位置（保持有序）：

// Java：查找插入位置（LeetCode 35）
public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

4.4 查找旋转排序数组中的目标

// Java：旋转排序数组查找（LeetCode 33）
public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;

        // 判断哪半边是有序的
        if (nums[left] <= nums[mid]) {
            // 左半边有序
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // 右半边有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

4.5 二分答案（搜索答案空间）

当问题满足单调性（答案越大/越小时，条件越容易/越难满足），可以用二分搜索答案：

# Python：分割数组的最大值（LeetCode 410）
# 将数组分成 m 个子数组，最小化最大子数组和
def splitArray(nums, m):
    def can_split(max_sum):
        count = 1
        current = 0
        for num in nums:
            if current + num > max_sum:
                count += 1
                current = num
            else:
                current += num
        return count <= m

    left, right = max(nums), sum(nums)
    while left < right:
        mid = left + (right - left) // 2
        if can_split(mid):
            right = mid
        else:
            left = mid + 1
    return left

4.6 浮点数二分

# Python：浮点数二分（求平方根）
def my_sqrt(x, epsilon=1e-7):
    if x < 0:
        return None
    left, right = 0, max(1, x)
    while right - left > epsilon:
        mid = (left + right) / 2
        if mid * mid < x:
            left = mid
        else:
            right = mid
    return (left + right) / 2

# 或者用固定迭代次数
def my_sqrt_iter(x, iterations=100):
    left, right = 0, max(1, x)
    for _ in range(iterations):
        mid = (left + right) / 2
        if mid * mid < x:
            left = mid
        else:
            right = mid
    return (left + right) / 2

5. 二分查找模板总结

5.1 两大模板

模板一：闭区间 [left, right]

int left = 0, right = arr.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}
return -1;

模板二：半开区间 [left, right)

int left = 0, right = arr.length;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
}
// left 是第一个 >= target 的位置

5.2 选择指南

6. 插值查找

6.1 插值查找原理

二分查找每次固定取中点，但当数据均匀分布时，可以根据目标值的大小估算其位置：

二分查找:  mid = left + (right - left) / 2
插值查找:  mid = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left])

类比查字典：找 “apple” 会翻到前面，找 “zoo” 会翻到后面，而不是每次翻到中间。

6.2 插值查找实现

// Java：插值查找
public int interpolationSearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;

    while (left <= right && target >= arr[left] && target <= arr[right]) {
        // 防止除零
        if (arr[left] == arr[right]) {
            if (arr[left] == target) return left;
            break;
        }

        // 插值公式
        int mid = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left]);

        // 边界检查
        if (mid < left || mid > right) break;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

# Python：插值查找
def interpolation_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right and arr[left] <= target <= arr[right]:
        if arr[left] == arr[right]:
            return left if arr[left] == target else -1

        # 插值公式
        mid = left + (target - arr[left]) * (right - left) // (arr[right] - arr[left])

        if mid < left or mid > right:
            break

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

6.3 复杂度分析

适用场景：数据量大且分布均匀的有序表，如年龄表、成绩表等。

7. 斐波那契查找

7.1 斐波那契查找原理

斐波那契查找利用斐波那契数列对有序表进行分割，与二分查找的区别在于分割点的选择：

• 二分查找：mid = (left + right) / 2
• 斐波那契查找：mid = left + F[k-1] - 1

其中 F[k] 是大于等于数组长度的最小斐波那契数。

斐波那契数列: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

核心思想：
- 将长度为 F[k]-1 的数组分为：
  左子数组: F[k-1]-1 个元素
  中间元素: 1 个
  右子数组: F[k-2]-1 个元素
- F[k]-1 = (F[k-1]-1) + 1 + (F[k-2]-1)

7.2 斐波那契查找实现

// Java：斐波那契查找
public int fibonacciSearch(int[] arr, int target) {
    int n = arr.length;
    int[] fib = generateFib(n);

    // 找到大于等于 n 的最小斐波那契数
    int k = 0;
    while (fib[k] - 1 < n) k++;

    // 扩展数组到 F[k]-1 的长度
    int[] temp = Arrays.copyOf(arr, fib[k] - 1);
    for (int i = n; i < temp.length; i++) {
        temp[i] = arr[n - 1]; // 用最后一个元素填充
    }

    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + fib[k - 1] - 1;
        if (temp[mid] == target) {
            return Math.min(mid, n - 1); // 处理填充位置
        } else if (temp[mid] < target) {
            left = mid + 1;
            k -= 2; // 右子数组长度为 F[k-2]-1
        } else {
            right = mid - 1;
            k -= 1; // 左子数组长度为 F[k-1]-1
        }
    }
    return -1;
}

private int[] generateFib(int max) {
    int[] fib = new int[max + 2];
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i <= max + 1; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib;
}

# Python：斐波那契查找
def fibonacci_search(arr, target):
    n = len(arr)

    # 生成斐波那契数列
    fib = [1, 1]
    while fib[-1] < n:
        fib.append(fib[-1] + fib[-2])

    k = len(fib) - 1

    # 扩展数组
    temp = arr + [arr[-1]] * (fib[k] - 1 - n)

    left, right = 0, n - 1
    while left <= right:
        mid = left + fib[k - 1] - 1
        if temp[mid] == target:
            return min(mid, n - 1)
        elif temp[mid] < target:
            left = mid + 1
            k -= 2
        else:
            right = mid - 1
            k -= 1

    return -1

7.3 斐波那契查找特点

与二分查找的区别：

• 二分查找每次等分（1:1），斐波那契查找按黄金分割比分割
• 斐波那契查找只做加减法，在某些硬件上更快
• 实际应用中，现代 CPU 的除法已很快，斐波那契查找的优势不明显

8. 各查找算法对比

9. 二分查找常见面试题

9.1 x 的平方根

// Java：x 的平方根（LeetCode 69）
public int mySqrt(int x) {
    if (x <= 1) return x;
    int left = 1, right = x / 2;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (mid == x / mid) return mid;       // mid * mid == x（防溢出用除法）
        else if (mid < x / mid) left = mid + 1;
        else right = mid - 1;
    }
    return right; // right 是最大的满足 mid*mid <= x 的值
}

9.2 寻找峰值

// Java：寻找峰值（LeetCode 162）
public int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1; // 峰值在右侧
        } else {
            right = mid;    // 峰值在左侧（含 mid）
        }
    }
    return left;
}

9.3 在排序矩阵中查找

# Python：搜索二维矩阵 II（LeetCode 240）
def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1  # 从右上角开始

    while row < m and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1  # 当前值太小，向下
        else:
            col -= 1  # 当前值太大，向左
    return False

9.4 求排序数组中目标的出现次数

// Java：目标在排序数组中的出现次数
public int countOccurrences(int[] nums, int target) {
    int first = findFirst(nums, target);
    if (first == -1) return 0;
    int last = findLast(nums, target);
    return last - first + 1;
}

private int findFirst(int[] nums, int target) {
    int left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            right = mid - 1; // 继续向左找
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

private int findLast(int[] nums, int target) {
    int left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            left = mid + 1; // 继续向右找
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

10. 二分查找的易错点

10.1 循环条件

// 闭区间 [left, right]：用 <=
while (left <= right) { ... }

// 半开区间 [left, right)：用 <
while (left < right) { ... }

10.2 边界更新

// 闭区间：left 和 right 都要跳过 mid
left = mid + 1;
right = mid - 1;

// 半开区间：right 不跳过 mid
left = mid + 1;
right = mid;  // 因为 right 是开区间

10.3 死循环陷阱

//  死循环：当 left = right - 1 时，mid = left，若 left = mid 则不变
while (left < right) {
    int mid = left + (right - left) / 2;
    if (condition) left = mid;    // 危险！
    else right = mid - 1;
}

//  修复：向上取整
int mid = left + (right - left + 1) / 2;

10.4 溢出检查

//  溢出风险
int mid = (left + right) / 2;

//  安全
int mid = left + (right - left) / 2;

11. 总结

查找算法的选择取决于数据特征和操作需求：

• 无序数据：顺序查找 O(n)，或先排序再二分
• 有序静态数据：二分查找 O(log n)，是实际工程中最常用的查找算法
• 均匀分布有序数据：插值查找 O(log log n)，但最坏 O(n)
• 动态数据：哈希表 O(1) 或平衡搜索树 O(log n)

二分查找是算法面试的高频考点，掌握其标准模板和变体（lower_bound、upper_bound、二分答案）至关重要。理解半开区间 [left, right) 的设计思想，可以避免大多数边界错误。