二分查找算法 - 计算机科学学习平台

📋 知识点概述

核心概念：二分查找就像在字典里查单词，每次打开中间页，根据字母顺序决定往前翻还是往后翻，每次都能排除一半的内容，快速定位目标！

🔤 关键术语：

有序数组 - 前提条件，数组必须已排序
搜索区间 - 当前查找的范围[left, right]
中间元素 - mid = (left + right) / 2
时间复杂度 - O(log n)，对数级别
空间复杂度 - O(1)，只需几个变量

📊 学习难度：入门

前置知识：数组、循环、条件判断

🔍 概念详解

📚 生活类比：猜数字游戏

朋友心里想了1-100之间的数字，让你猜：

🎯 第一次猜50，朋友说"太大了"
➡️ 范围缩小到1-49
🎯 第二次猜25，朋友说"太小了"
➡️ 范围缩小到26-49
🎯 继续二分，最多7次就能猜中（log₂100 ≈ 7）
💡 比从1开始逐个猜（最多100次）快得多！

1️⃣ 算法原理

核心思想：利用数组的有序性，每次比较中间元素，排除一半的搜索空间。

mid = left + (right - left) / 2
避免(left + right)溢出的写法

三种情况：

arr[mid] == target：找到目标，返回索引
arr[mid] < target：目标在右半部分，left = mid + 1
arr[mid] > target：目标在左半部分，right = mid - 1

2️⃣ 时间复杂度分析

为什么是O(log n)？

第1次比较后，剩余 n/2 个元素
第2次比较后，剩余 n/4 个元素
第3次比较后，剩余 n/8 个元素
第k次比较后，剩余 n/2^k 个元素
当 n/2^k = 1 时，k = log₂n

具体例子：

数组大小	最多比较次数	线性查找
10	4	10
100	7	100
1,000	10	1,000
1,000,000	20	1,000,000

3️⃣ 算法执行步骤

1 初始化：left = 0, right = n - 1

2 计算中间位置：mid = left + (right - left) / 2

3 比较arr[mid]与target

4 根据比较结果调整left或right

5 重复2-4直到找到或left > right

⚠️ 初学者易错点

边界条件：是 left <= right 还是 left < right？
更新边界：是 mid 还是 mid ± 1？
整数溢出：mid = (left + right) / 2 可能溢出
数组必须有序：这是前提条件！
重复元素：标准二分找到的可能不是第一个

📊 可视化展示

🎯 二分查找动态演示

查找目标：

数组大小：

当前比较

等待开始查找...

速度： 1000ms

0

比较次数

-

左边界

-

右边界

-

中间位置

查找历史

💻 代码实现

def binary_search(arr, target):
    """
    标准二分查找
    Args:
        arr: 有序数组
        target: 查找目标
    Returns:
        目标元素的索引，如果不存在返回-1
    """
    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  # 未找到


def binary_search_recursive(arr, target, left=0, right=None):
    """
    递归版本的二分查找
    """
    if right is None:
        right = len(arr) - 1

    if left > right:
        return -1

    mid = left + (right - left) // 2

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


def binary_search_first(arr, target):
    """
    查找第一个等于target的元素
    用于处理有重复元素的情况
    """
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            result = mid
            right = mid - 1  # 继续在左边查找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result


def binary_search_last(arr, target):
    """
    查找最后一个等于target的元素
    """
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            result = mid
            left = mid + 1  # 继续在右边查找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result


def binary_search_insert_position(arr, target):
    """
    查找插入位置
    返回target应该插入的位置，保持数组有序
    """
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2

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

    return left


def binary_search_range(arr, target):
    """
    查找目标元素的范围 [first, last]
    """
    first = binary_search_first(arr, target)
    if first == -1:
        return [-1, -1]

    last = binary_search_last(arr, target)
    return [first, last]


def binary_search_rotated(arr, target):
    """
    在旋转排序数组中查找
    例如：[4,5,6,7,0,1,2]
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid

        # 判断哪一半是有序的
        if arr[left] <= arr[mid]:  # 左半部分有序
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半部分有序
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1


def binary_search_peak(arr):
    """
    寻找峰值元素
    峰值：大于左右相邻元素的元素
    """
    left, right = 0, len(arr) - 1

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] < arr[mid + 1]:
            left = mid + 1  # 峰值在右边
        else:
            right = mid  # 峰值在左边或就是mid

    return left


def binary_search_2d_matrix(matrix, target):
    """
    在二维矩阵中查找
    矩阵每行递增，每行的第一个元素大于上一行的最后一个元素
    """
    if not matrix or not matrix[0]:
        return False

    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1

    while left <= right:
        mid = left + (right - left) // 2
        # 将一维索引转换为二维坐标
        row, col = mid // n, mid % n

        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            left = mid + 1
        else:
            right = mid - 1

    return False


# 测试示例
if __name__ == "__main__":
    # 基础测试
    arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
    print("数组:", arr)

    # 标准二分查找
    target = 7
    result = binary_search(arr, target)
    print(f"查找 {target}: 索引 = {result}")

    # 递归版本
    result = binary_search_recursive(arr, target)
    print(f"递归查找 {target}: 索引 = {result}")

    # 有重复元素的情况
    arr_dup = [1, 2, 2, 2, 3, 4, 4, 5]
    print(f"\n有重复元素的数组: {arr_dup}")
    print(f"第一个2的位置: {binary_search_first(arr_dup, 2)}")
    print(f"最后一个2的位置: {binary_search_last(arr_dup, 2)}")
    print(f"2的范围: {binary_search_range(arr_dup, 2)}")

    # 插入位置
    print(f"\n插入3.5的位置: {binary_search_insert_position(arr, 8)}")

    # 旋转数组
    rotated = [4, 5, 6, 7, 0, 1, 2]
    print(f"\n旋转数组: {rotated}")
    print(f"查找0: {binary_search_rotated(rotated, 0)}")

    # 寻找峰值
    peak_arr = [1, 2, 3, 1]
    print(f"\n数组 {peak_arr} 的峰值索引: {binary_search_peak(peak_arr)}")

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 标准二分查找
int binarySearch(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;  // 未找到
}

// 递归版本
int binarySearchRecursive(vector<int>& arr, int target, int left, int right) {
    if (left > right) {
        return -1;
    }

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

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

// 查找第一个等于target的元素
int binarySearchFirst(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            result = mid;
            right = mid - 1;  // 继续在左边查找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

// 查找最后一个等于target的元素
int binarySearchLast(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            result = mid;
            left = mid + 1;  // 继续在右边查找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

// 查找插入位置
int searchInsertPosition(vector<int>& arr, int target) {
    int left = 0, right = arr.size();

    while (left < right) {
        int mid = left + (right - left) / 2;

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

    return left;
}

// 查找元素范围
vector<int> searchRange(vector<int>& arr, int target) {
    int first = binarySearchFirst(arr, target);
    if (first == -1) {
        return {-1, -1};
    }

    int last = binarySearchLast(arr, target);
    return {first, last};
}

// 在旋转排序数组中查找
int searchRotated(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;
        }

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

    return -1;
}

// 寻找峰值
int findPeakElement(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] < arr[mid + 1]) {
            left = mid + 1;  // 峰值在右边
        } else {
            right = mid;  // 峰值在左边或就是mid
        }
    }

    return left;
}

// 二分查找模板类（支持自定义比较）
template<typename T>
class BinarySearcher {
public:
    // 标准二分查找
    static int search(const vector<T>& arr, const T& 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;
    }

    // 使用自定义比较函数
    template<typename Compare>
    static int searchWithCompare(const vector<T>& arr, const T& target, Compare comp) {
        int left = 0, right = arr.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (!comp(arr[mid], target) && !comp(target, arr[mid])) {
                return mid;  // 相等
            } else if (comp(arr[mid], target)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
};

// 打印数组
void printArray(const vector<int>& arr) {
    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;
}

int main() {
    // 基础测试
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    cout << "数组: ";
    printArray(arr);

    // 标准二分查找
    int target = 7;
    int result = binarySearch(arr, target);
    cout << "查找 " << target << ": 索引 = " << result << endl;

    // 递归版本
    result = binarySearchRecursive(arr, target, 0, arr.size() - 1);
    cout << "递归查找 " << target << ": 索引 = " << result << endl;

    // 有重复元素
    vector<int> arrDup = {1, 2, 2, 2, 3, 4, 4, 5};
    cout << "\n有重复元素的数组: ";
    printArray(arrDup);
    cout << "第一个2的位置: " << binarySearchFirst(arrDup, 2) << endl;
    cout << "最后一个2的位置: " << binarySearchLast(arrDup, 2) << endl;

    auto range = searchRange(arrDup, 2);
    cout << "2的范围: [" << range[0] << ", " << range[1] << "]" << endl;

    // 插入位置
    cout << "\n在原数组中插入8的位置: " << searchInsertPosition(arr, 8) << endl;

    // 旋转数组
    vector<int> rotated = {4, 5, 6, 7, 0, 1, 2};
    cout << "\n旋转数组: ";
    printArray(rotated);
    cout << "查找0: " << searchRotated(rotated, 0) << endl;

    // 寻找峰值
    vector<int> peakArr = {1, 2, 3, 1};
    cout << "\n数组 ";
    printArray(peakArr);
    cout << "峰值索引: " << findPeakElement(peakArr) << endl;

    // 使用模板类
    cout << "\n使用模板类查找: " << BinarySearcher<int>::search(arr, 13) << endl;

    return 0;
}

import java.util.*;

public class BinarySearch {

    // 标准二分查找
    public static 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;  // 未找到
    }

    // 递归版本
    public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1;
        }

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

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

    // 查找第一个等于target的元素
    public static int binarySearchFirst(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                result = mid;
                right = mid - 1;  // 继续在左边查找
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }

    // 查找最后一个等于target的元素
    public static int binarySearchLast(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                result = mid;
                left = mid + 1;  // 继续在右边查找
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }

    // 查找插入位置
    public static int searchInsertPosition(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;
            }
        }

        return left;
    }

    // 查找元素范围
    public static int[] searchRange(int[] arr, int target) {
        int first = binarySearchFirst(arr, target);
        if (first == -1) {
            return new int[]{-1, -1};
        }

        int last = binarySearchLast(arr, target);
        return new int[]{first, last};
    }

    // 在旋转排序数组中查找
    public static int searchRotated(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;
            }

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

        return -1;
    }

    // 寻找峰值
    public static int findPeakElement(int[] arr) {
        int left = 0, right = arr.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;  // 峰值在右边
            } else {
                right = mid;  // 峰值在左边或就是mid
            }
        }

        return left;
    }

    // 二分查找的泛型实现
    public static <T extends Comparable<T>> int binarySearchGeneric(T[] arr, T target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int cmp = arr[mid].compareTo(target);

            if (cmp == 0) {
                return mid;
            } else if (cmp < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

    // 打印数组
    public static void printArray(int[] arr) {
        System.out.println(Arrays.toString(arr));
    }

    public static void main(String[] args) {
        // 基础测试
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        System.out.print("数组: ");
        printArray(arr);

        // 标准二分查找
        int target = 7;
        int result = binarySearch(arr, target);
        System.out.println("查找 " + target + ": 索引 = " + result);

        // 递归版本
        result = binarySearchRecursive(arr, target, 0, arr.length - 1);
        System.out.println("递归查找 " + target + ": 索引 = " + result);

        // 有重复元素
        int[] arrDup = {1, 2, 2, 2, 3, 4, 4, 5};
        System.out.print("\n有重复元素的数组: ");
        printArray(arrDup);
        System.out.println("第一个2的位置: " + binarySearchFirst(arrDup, 2));
        System.out.println("最后一个2的位置: " + binarySearchLast(arrDup, 2));

        int[] range = searchRange(arrDup, 2);
        System.out.println("2的范围: " + Arrays.toString(range));

        // 插入位置
        System.out.println("\n在原数组中插入8的位置: " + searchInsertPosition(arr, 8));

        // 旋转数组
        int[] rotated = {4, 5, 6, 7, 0, 1, 2};
        System.out.print("\n旋转数组: ");
        printArray(rotated);
        System.out.println("查找0: " + searchRotated(rotated, 0));

        // 寻找峰值
        int[] peakArr = {1, 2, 3, 1};
        System.out.print("\n数组 ");
        printArray(peakArr);
        System.out.println("峰值索引: " + findPeakElement(peakArr));

        // 使用泛型
        Integer[] integerArr = {1, 3, 5, 7, 9};
        System.out.println("\n泛型查找5: " + binarySearchGeneric(integerArr, 5));

        // 使用Java内置的二分查找
        System.out.println("\nJava Arrays.binarySearch: " +
                          Arrays.binarySearch(arr, 13));
    }
}

🌟 实际应用

📚 字典查询

电子词典、数据库索引等使用二分查找快速定位

🎮 游戏开发

在排行榜中快速查找玩家排名，碰撞检测优化

💾 文件系统

在已排序的文件列表中快速查找文件

🔢 数值计算

求平方根、方程求解等数值方法

📊 数据分析

在时间序列数据中查找特定时间点的数据

🏭 工业控制

在传感器数据中快速定位异常值

✅ 学习检验

❓ 问题1：二分查找的前提条件是什么？为什么需要这些条件？

答案：二分查找需要两个前提条件：

1. 数组必须有序

原因：只有有序才能确定目标在哪一半
如果无序，比较结果无法指导搜索方向

2. 支持随机访问（数组结构）

原因：需要O(1)时间访问中间元素
链表不适合，访问中间节点需要O(n)

额外考虑：

数据量较大时才有优势（小数据量线性查找可能更快）
静态或很少变化的数据（频繁插入删除会破坏有序性）

❓ 问题2：while (left <= right) 和 while (left < right) 的区别？

答案：这是二分查找最常见的边界问题。

while (left <= right)：

搜索区间：[left, right]，两端都包含
终止条件：left > right，区间为空
更新方式：left = mid + 1, right = mid - 1
适用：标准的查找某个值

while (left < right)：

搜索区间：[left, right)，左闭右开
终止条件：left == right
更新方式：left = mid + 1, right = mid
适用：查找边界位置

示例对比：

// 标准查找
while (left <= right) {
    mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}

// 查找左边界
while (left < right) {
    mid = left + (right - left) / 2;
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
}

❓ 问题3：为什么要写 mid = left + (right - left) / 2 而不是 mid = (left + right) / 2？

答案：防止整数溢出！

问题分析：

当left和right都很大时，left + right可能超过整数最大值
例如：left = 2^30, right = 2^30，相加会溢出
溢出后结果变成负数，导致程序错误

解决方案：

mid = left + (right - left) / 2（推荐）
mid = left + ((right - left) >> 1)（位运算版本）
mid = (left + right) >>> 1（Java无符号右移）

其他语言的处理：

Python：整数无限大，不存在溢出问题
JavaScript：使用Math.floor((left + right) / 2)

❓ 问题4：如何用二分查找解决"寻找旋转数组的最小值"问题？

答案：利用旋转数组的特性进行二分。

问题描述：

数组原本有序，被旋转了若干位。如：[4,5,6,7,0,1,2]

解题思路：

最小值一定在"断层"处
比较mid与right：
- arr[mid] > arr[right]：最小值在右半部分
- arr[mid] < arr[right]：最小值在左半部分（包括mid）
- arr[mid] == arr[right]：无法判断，right--

代码实现：

def findMin(arr):
    left, right = 0, len(arr) - 1

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] > arr[right]:
            left = mid + 1  # 最小值在右边
        elif arr[mid] < arr[right]:
            right = mid     # 最小值在左边或就是mid
        else:
            right -= 1      # 处理重复元素

    return arr[left]

时间复杂度：O(log n)，有重复时最坏O(n)

📚 进阶学习建议

掌握变种：查找第一个/最后一个、查找范围
扩展应用：二分答案、三分查找
相关算法：快速选择、插值查找
实战练习：LeetCode二分查找专题