GB3-有序表中的二分查找¶

算法原理¶

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。其核心思想是通过比较目标值与中间元素，每次将搜索范围缩小一半，从而快速定位目标元素。

前提条件¶

数组必须有序（升序或降序）
支持随机访问（如数组结构）

核心思想¶

每次比较后，搜索范围减半： - 如果中间元素等于目标值：找到目标 - 如果中间元素小于目标值：在右半部分继续查找 - 如果中间元素大于目标值：在左半部分继续查找

非递归实现¶

C
/**
 * 非递归二分查找函数
 * 参数：L - 顺序表，key - 查找的目标值
 * 返回值：找到返回位置（1-based），未找到返回-1
 */
int binsearch(Sqlist L, int key) {
    // 初始化搜索边界
    int low = 0;              // 搜索下界（包含）
    int high = L.length - 1;  // 搜索上界（包含）
    int mid;                  // 中间位置

    // 当搜索范围有效时继续查找
    while (low <= high) {
        // 计算中间位置（避免整数溢出的写法：mid = low + (high - low) / 2）
        mid = (low + high) / 2;

        // 找到目标元素
        if (L.data[mid] == key) {
            return mid + 1;  // 返回1-based位置
        }
        // 目标值在右半部分
        else if (L.data[mid] < key) {
            low = mid + 1;   // 缩小搜索范围到右半部分
        }
        // 目标值在左半部分
        else {
            high = mid - 1;  // 缩小搜索范围到左半部分
        }
    }

    // 未找到目标元素
    return -1;
}

递归实现¶

C
/**
 * 递归二分查找函数
 * 参数：L - 顺序表，key - 查找的目标值，low - 搜索下界，high - 搜索上界
 * 返回值：找到返回位置（1-based），未找到返回-1
 */
int func(Sqlist L, int key, int low, int high) {
    // 递归终止条件：搜索范围无效
    if (low > high) {
        return -1;  // 未找到目标元素
    }

    // 计算中间位置
    int mid = (low + high) / 2;

    // 找到目标元素
    if (L.data[mid] == key) {
        return mid + 1;  // 返回1-based位置
    }
    // 目标值在右半部分，递归搜索右半部分
    else if (L.data[mid] < key) {
        return func(L, key, mid + 1, high);
    }
    // 目标值在左半部分，递归搜索左半部分
    else {
        return func(L, key, low, mid - 1);
    }
}

/**
 * 递归二分查找的包装函数
 */
int binary_search_recursive(Sqlist L, int key) {
    return func(L, key, 0, L.length - 1);
}

执行过程详解¶

示例演示¶

C
// 有序数组：[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
// 查找 key = 7

// 非递归执行过程：
// 初始：low=0, high=9
// 第1次：mid=4, data[4]=9 > 7 → high=3
// 第2次：mid=1, data[1]=3 < 7 → low=2  
// 第3次：mid=2, data[2]=5 < 7 → low=3
// 第4次：mid=3, data[3]=7 = 7 → 找到，返回4

// 递归执行过程：
// func(L, 7, 0, 9)
// ├── mid=4, 9>7 → func(L, 7, 0, 3)
// │   ├── mid=1, 3<7 → func(L, 7, 2, 3)
// │   │   ├── mid=2, 5<7 → func(L, 7, 3, 3)
// │   │   │   └── mid=3, 7=7 → 返回4
// │   │   └── 返回4
// │   └── 返回4
// └── 返回4

复杂度分析¶

时间复杂度¶

1. 最好情况¶

O(1)：第一次比较就找到目标元素

2. 最坏情况¶

每次都将搜索范围减半
设 n 个元素，最多需要 ⌈log₂n⌉ 次比较
O(log N)

3. 平均情况¶

平均需要 (log₂n - 1) 次比较
O(log N)

空间复杂度¶

非递归版本¶

只使用常数个局部变量
O(1)

递归版本¶

递归深度为 O(log N)
每次递归调用占用 O(1) 栈空间
O(log N)

算法正确性证明¶

循环不变式证明¶

对于非递归版本，定义循环不变式： - 初始化：循环开始前，如果目标存在，则在 [low, high] 范围内 - 保持：每次迭代后，如果目标存在，则仍在 [low, high] 范围内 - 终止：循环结束时，要么找到目标，要么确定目标不存在

递归正确性¶

基础情况：low > high 时返回 -1，正确
递归情况：根据比较结果缩小搜索范围，保持问题规模递减

边界条件处理¶

C
// 关键边界处理：

// 1. 空数组处理
if (L.length == 0) return -1;

// 2. 单元素数组
// low = high = 0，正常处理

// 3. 目标值在数组范围外
// 如查找 0 或 20，在 [1,19] 中，最终 low > high

// 4. 重复元素处理
// 返回其中一个位置，具体哪个取决于实现细节

优化版本¶

1. 防止整数溢出版本¶

C
int binsearch_safe(Sqlist L, int key) {
    int low = 0, high = L.length - 1;

    while (low <= high) {
        // 防止 (low + high) 溢出的写法
        int mid = low + (high - low) / 2;

        if (L.data[mid] == key) {
            return mid + 1;
        } else if (L.data[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

2. 查找插入位置版本¶

C
// 查找目标值应该插入的位置（保持有序）
int search_insert_position(Sqlist L, int key) {
    int low = 0, high = L.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (L.data[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low + 1;  // 返回1-based插入位置
}

3. 查找第一个/最后一个出现位置¶

C
// 查找第一个等于key的位置
int find_first(Sqlist L, int key) {
    int low = 0, high = L.length - 1;
    int result = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (L.data[mid] == key) {
            result = mid + 1;
            high = mid - 1;  // 继续在左半部分查找
        } else if (L.data[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

// 查找最后一个等于key的位置
int find_last(Sqlist L, int key) {
    int low = 0, high = L.length - 1;
    int result = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (L.data[mid] == key) {
            result = mid + 1;
            low = mid + 1;   // 继续在右半部分查找
        } else if (L.data[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

实际应用场景¶

1. 数据库索引查找¶

C
// 在B+树索引中查找记录
int find_record_in_index(IndexNode* index, int key) {
    return binsearch(index->keys, key);
}

2. 游戏排行榜查找¶

C
// 查找玩家在排行榜中的位置
int find_player_rank(SortedList players, int player_id) {
    return binsearch(players, player_id);
}

3. 字典查找¶

C
// 在有序词典中查找单词
int lookup_word(Dictionary dict, char* word) {
    return binsearch(dict.words, word);
}

与其他查找算法的比较¶

算法	时间复杂度	空间复杂度	适用场景
顺序查找	O(N)	O(1)	无序数据
二分查找	O(log N)	O(1)	有序数据
哈希查找	O(1) 平均	O(N)	需要额外空间
二叉搜索树	O(log N) 平均	O(N)	动态数据

理论扩展¶

1. 三分查找¶

C
// 在单峰函数中查找极值点
int ternary_search(int arr[], int low, int high) {
    while (high - low > 2) {
        int mid1 = low + (high - low) / 3;
        int mid2 = high - (high - low) / 3;

        if (arr[mid1] < arr[mid2]) {
            low = mid1;
        } else {
            high = mid2;
        }
    }
    return (low + high) / 2;
}

2. 指数查找¶

C
// 适用于无限长或长度未知的有序序列
int exponential_search(Sqlist L, int key) {
    if (L.data[0] == key) return 1;

    int bound = 1;
    while (bound < L.length && L.data[bound] < key) {
        bound *= 2;
    }

    return binsearch_range(L, key, bound/2, 
                          min(bound, L.length-1));
}

3. 插值查找¶

C
// 利用数据分布特性优化查找位置
int interpolation_search(Sqlist L, int key) {
    int low = 0, high = L.length - 1;

    while (low <= high && key >= L.data[low] && key <= L.data[high]) {
        if (low == high) {
            return (L.data[low] == key) ? low + 1 : -1;
        }

        // 插值公式计算预测位置
        int pos = low + ((double)(key - L.data[low]) / 
                        (L.data[high] - L.data[low])) * (high - low);

        if (L.data[pos] == key) {
            return pos + 1;
        } else if (L.data[pos] < key) {
            low = pos + 1;
        } else {
            high = pos - 1;
        }
    }
    return -1;
}

总结¶

二分查找是计算机科学中最基础也是最重要的算法之一：

核心优势¶

高效性：O(log N) 时间复杂度
简洁性：实现简单，逻辑清晰
稳定性：性能稳定，不受数据分布影响

关键要点¶

前提条件：数据必须有序
边界处理：正确处理各种边界情况
实现选择：非递归版本空间效率更高

应用广泛¶

数据库索引
算法竞赛
系统编程
数据分析

二分查找体现了分治思想的精髓，通过不断缩小问题规模来达到高效求解的目的，是算法设计中的经典范例。