programming

二分查找算法：高效的有序数组搜索技术

算法原理

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它采用分治策略，通过不断将搜索范围缩小一半来快速定位目标元素。

基本思想

  1. 比较目标值与数组中间元素
  2. 如果相等，返回中间位置
  3. 如果目标值小于中间元素，在左半部分继续搜索
  4. 如果目标值大于中间元素，在右半部分继续搜索
  5. 重复此过程直到找到目标或搜索范围为空

算法步骤

1
2
3
4
5
6
7
1. 设置左边界 left = 0，右边界 right = n-1
2. 当 left <= right 时：
   a. 计算中间位置 mid = (left + right) / 2
   b. 如果 arr[mid] == target，返回 mid
   c. 如果 arr[mid] > target，设置 right = mid - 1
   d. 如果 arr[mid] < target，设置 left = mid + 1
3. 如果未找到，返回 -1

优缺点分析

优点

  1. 时间复杂度低：O(log n)，远优于线性搜索的O(n)
  2. 空间复杂度低：O(1)，只需要常数额外空间
  3. 效率稳定：最坏情况下的性能可预测
  4. 实现简单：算法逻辑清晰，易于编码

缺点

  1. 要求数组有序：只能在已排序的数组中使用
  2. 不适合频繁插入删除：维护有序性成本高
  3. 不支持链表：需要随机访问特性
  4. 对小数据集效果不明显：常数因子可能使其不如线性搜索

使用场景

适用场景

  1. 大规模有序数据查找：如数据库索引、字典查找
  2. 游戏开发：排行榜查找、资源索引
  3. 算法竞赛：作为基础工具解决复杂问题
  4. 系统编程：内存地址查找、文件系统索引

实际应用

  • 数据库B+树索引
  • 编程语言标准库（如C++的binary_search）
  • 操作系统内存管理
  • 网络路由表查找

C语言实现

迭代版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <stdio.h>

/**
 * 二分查找 - 迭代实现
 * @param arr 有序数组
 * @param size 数组大小
 * @param target 目标值
 * @return 目标值的索引，未找到返回-1
 */
int binary_search_iterative(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return -1; // 未找到
}

/**
 * 二分查找 - 递归实现
 * @param arr 有序数组
 * @param left 左边界
 * @param right 右边界
 * @param target 目标值
 * @return 目标值的索引，未找到返回-1
 */
int binary_search_recursive(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        return binary_search_recursive(arr, left, mid - 1, target);
    } else {
        return binary_search_recursive(arr, mid + 1, right, target);
    }
}

/**
 * 查找第一个大于等于target的元素位置
 */
int binary_search_lower_bound(int arr[], int size, int target) {
    int left = 0;
    int right = size;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

/**
 * 查找第一个大于target的元素位置
 */
int binary_search_upper_bound(int arr[], int size, int target) {
    int left = 0;
    int right = size;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

// 测试函数
void test_binary_search() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("数组: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
    
    // 测试基本二分查找
    int targets[] = {7, 12, 1, 19, 20};
    int num_targets = sizeof(targets) / sizeof(targets[0]);
    
    for (int i = 0; i < num_targets; i++) {
        int target = targets[i];
        int result1 = binary_search_iterative(arr, size, target);
        int result2 = binary_search_recursive(arr, 0, size - 1, target);
        
        printf("查找 %d:\n", target);
        printf("  迭代版本: %s\n", 
               result1 != -1 ? "找到" : "未找到");
        printf("  递归版本: %s\n", 
               result2 != -1 ? "找到" : "未找到");
        
        if (result1 != -1) {
            printf("  位置: %d, 值: %d\n", result1, arr[result1]);
        }
        printf("\n");
    }
    
    // 测试边界查找
    printf("边界查找测试:\n");
    for (int i = 0; i < num_targets; i++) {
        int target = targets[i];
        int lower = binary_search_lower_bound(arr, size, target);
        int upper = binary_search_upper_bound(arr, size, target);
        
        printf("目标 %d: lower_bound=%d, upper_bound=%d\n", 
               target, lower, upper);
    }
}

int main() {
    printf("=== 二分查找算法演示 ===\n\n");
    test_binary_search();
    return 0;
}

算法变种

1. 查找插入位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int search_insert_position(int arr[], int size, int target) {
    int left = 0, right = 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 left; // 插入位置
}

2. 在旋转数组中查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int search_in_rotated_array(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        
        // 判断哪一半是有序的
        if (arr[left] <= arr[mid]) {
            // 左半部分有序
            if (target >= arr[left] && target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // 右半部分有序
            if (target > arr[mid] && target <= arr[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

性能分析

时间复杂度

  • 最好情况：O(1) - 目标元素正好在中间
  • 最坏情况：O(log n) - 需要搜索到最后一层
  • 平均情况：O(log n)

空间复杂度

  • 迭代版本：O(1)
  • 递归版本：O(log n) - 递归调用栈

性能比较

数组大小 线性搜索(最坏) 二分搜索(最坏)
1,000 1,000 10
1,000,000 1,000,000 20
1,000,000,000 1,000,000,000 30

总结

二分查找是计算机科学中最基础且重要的算法之一。它体现了分治思想的精髓，在处理大规模有序数据时展现出卓越的性能。虽然有使用前提限制，但在合适的场景下，二分查找是不可替代的高效工具。

掌握二分查找不仅有助于解决实际问题，更重要的是理解其背后的算法思维，为学习更复杂的算法和数据结构奠定基础。

版权所有，如有侵权请联系我