一、排序算法
高考考点
排序算法：冒泡排序法、选择排序法、插入排序法
一、排序是什么？
排序就是把一堆乱序的数字，按升序或降序排好。本文中涉及的案例默认升序排序。
比如：[5, 2, 8, 1, 9] → 排序后 → [1, 2, 5, 8, 9]
二、冒泡排序（Bubble Sort）
1.工作原理
冒泡排序通过反复比较相邻元素，将最大的元素一步步"冒泡"到数组末尾，从而实现排序。
初始：[5, 2, 8, 1, 9]
第1轮：比较相邻的两个数，大的往后移
[2, 5, 8, 1, 9] ← 5和2比较，交换
[2, 5, 1, 8, 9] ← 8和1比较，交换
[2, 5, 1, 8, 9] ← 8和9比较，不交换
最大的9已经"冒"到最后
第2轮：[2, 5, 1, 8, 9]
[2, 1, 5, 8, 9] ← 5和1比较，交换
[2, 1, 5, 8, 9] ← 5和8比较，不交换
次大的8到倒数第二
第3轮：[2, 1, 5, 8, 9]
[1, 2, 5, 8, 9] ← 2和1比较，交换
继续...
最终：[1, 2, 5, 8, 9]
2.代码实现
using System;
class Program
{
static void Main()
{
int[] arr = {5, 2, 8, 1, 9};
BubbleSort(arr);
Console.WriteLine(string.Join(",", arr)); // 输出：1,2,5,8,9
}
static public int[] BubbleSort(int[] arr)
{
// 防御性检查：避免传入空数组/长度为1的数组时报错
if (arr == null || arr.Length <= 1)
{
return arr;
}
for( int i = 0; i < arr.Length - 1; i++ )
{
// 内层循环：每轮冒泡后，最后i个元素已排好序，无需再比较
for ( int j = 0; j < arr.Length - 1 - i; j++ )
{
if( arr[j] > arr[j+1])
{
// 修复：正确的交换逻辑
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp; // 关键修正：赋值temp而非arr[j]
}
}
}
return arr;
}
}
3.输出结果
排序前：5, 2, 8, 1, 9
第1轮开始：
交换 5 和 2 → 2, 5, 8, 1, 9
交换 8 和 1 → 2, 5, 1, 8, 9
第2轮开始：
交换 5 和 1 → 2, 1, 5, 8, 9
第3轮开始：
交换 2 和 1 → 1, 2, 5, 8, 9
第4轮开始：
排序后：1, 2, 5, 8, 9
三、选择排序（Selection Sort）
1.选择排序是什么
每一轮只找最小的，放到当前最前面，重复到有序。
2.自然语言描述
以数组 [5, 3, 8, 4, 2] 为例：
初始状态：已排序区间为空，未排序区间为整个数组 → [] [5, 3, 8, 4, 2]
第 1 轮：
遍历未排序区间 [5, 3, 8, 4, 2]，找到最小值 2，记录其索引 4。
将最小值 2 与未排序区间的第一个元素 5 交换位置。
结果：已排序区间 [2]，未排序区间 [3, 8, 4, 5] → [2] [3, 8, 4, 5]
第 2 轮：
遍历未排序区间 [3, 8, 4, 5]，找到最小值 3，记录其索引 0（未排序区间内的索引）。
最小值 3 就是未排序区间的第一个元素，无需交换。
结果：已排序区间 [2, 3]，未排序区间 [8, 4, 5] → [2, 3] [8, 4, 5]
第 3 轮：
遍历未排序区间 [8, 4, 5]，找到最小值 4，记录其索引 1（未排序区间内的索引）。
将最小值 4 与未排序区间的第一个元素 8 交换位置。
结果：已排序区间 [2, 3, 4]，未排序区间 [8, 5] → [2, 3, 4] [8, 5]
第 4 轮：
遍历未排序区间 [8, 5]，找到最小值 5，记录其索引 1（未排序区间内的索引）。
将最小值 5 与未排序区间的第一个元素 8 交换位置。
结果：已排序区间 [2, 3, 4, 5]，未排序区间 [8] → [2, 3, 4, 5] [8]
结束：未排序区间只剩一个元素，默认有序，最终数组为 [2, 3, 4, 5, 8]。
3.代码实现
using System;
class SelectionSortExample
{
static void Main()
{
int[] numbers = { 5, 3, 8, 4, 2 };
// 选择排序
for (int i = 0; i < numbers.Length - 1; i++) // 外层：当前位置
{
int minIndex = i; // 假设当前位置是最小的
// 在剩下的数中找真正的最小值
for (int j = i + 1; j < numbers.Length; j++)
{
if (numbers[j] < numbers[minIndex])
{
minIndex = j;
}
}
// 如果找到的最小值不在当前位置，就交换
if (minIndex != i)
{
int temp = numbers[i];
numbers[i] = numbers[minIndex];
numbers[minIndex] = temp;
}
else
{
Console.WriteLine($" 最小值 {numbers[minIndex]} 已在正确位置");
}
}
Console.WriteLine("\n排序后：" + string.Join(", ", numbers));
}
}
四、插入排序（Insertion Sort）
1.工作原理
选择排序可以类比整理扑克牌的场景：
- 想象手里已经有一些未排好序的牌
- 每抓到一张新牌，你会从后往前对比手里的牌，把新牌插入到一个合适的位置，让手里的牌始终保持有序。
2.自然语言描述
以数组 [5, 3, 8, 4, 2] 为例
初始状态：已排序区间 [5]，未排序区间 [3, 8, 4, 2]
第 1 轮：
待插入元素：未排序区间第一个元素 3
从已排序区间末尾（元素 5）往前对比：3 < 5，将 5 后移一位，已排序区间变为 [5, 5]
已无更前面的元素，将 3 插入到最前面
结果：[3, 5] [8, 4, 2]
第 2 轮：
待插入元素：8
从已排序区间末尾（元素 5）往前对比：8 > 5，无需后移元素
直接将 8 插入到已排序区间末尾
结果：[3, 5, 8] [4, 2]
第 3 轮：
待插入元素：4
从已排序区间末尾（元素 8）往前对比：4 < 8，将 8 后移一位 → [3, 5, 8, 8]
继续往前对比：4 < 5，将 5 后移一位 → [3, 5, 5, 8]
继续往前对比：4 > 3，停止后移
将 4 插入到 3 和 5 之间
结果：[3, 4, 5, 8] [2]
第 4 轮：
待插入元素：2
从已排序区间末尾（元素 8）往前对比，依次将 8、5、4、3 后移一位 → [3, 3, 4, 5, 8]
已无更前面的元素，将 2 插入到最前面
结果：[2, 3, 4, 5, 8]（未排序区间为空，排序完成）
3.代码实现：
using System;
class InsertionSortExample
{
static void Main()
{
int[] arr = { 5, 3, 8, 4, 2 };
// 数组长度
int n = arr.Length;
// 外层循环：遍历未排序区间（从索引1开始，索引0为初始已排序区间）
for (int i = 1; i < n; i++)
{
// 步骤1：取出未排序区间的第一个元素（索引i）作为待插入元素
int insertValue = arr[i];
// 步骤2：定义已排序区间的末尾索引（初始为i-1，从后往前对比）
int j = i - 1;
// 内层循环：从后往前遍历已排序区间，找到待插入元素的合适位置
// 条件：1. j >= 0（不越界） 2. arr[j] > insertValue（当前元素比待插入元素大，需要后移）
while (j >= 0 && arr[j] > insertValue)
{
// 将当前元素后移一位，给待插入元素腾出空间
arr[j + 1] = arr[j];
// 索引往前移动，继续对比下一个元素
j--;
}
// 步骤3：将待插入元素插入到找到的合适位置（j+1，因为循环结束后j多减了1）
arr[j + 1] = insertValue;
}
}
}
运行结果
排序后的数组：2, 3, 4, 5, 8
4.算法评价
- 时间复杂度：
- 最好情况：O(n)（数组已经有序，内层 while 循环无需执行，只需外层遍历一次）。
- 最坏情况 / 平均情况：O(n²)（数组逆序，每个元素都需要遍历整个已排序区间）。
- 空间复杂度：O(1)，属于「原地排序」，无需额外辅助数组，仅用少量临时变量，空间效率高。
五、三种排序评价对比（重要！）
| 特性 | 冒泡排序 | 选择排序 | 插入排序 |
|---|---|---|---|
| 思想 | 相邻比较，大的往后 | 每次选最小的放前面 | 像插牌一样插入 |
| 时间复杂度 | O(n²) | O(n²) | O(n²) |
| 空间复杂度 | O(1) | O(1) | O(1) |
| 优点 | 简单易懂 | 交换次数少 | 对部分有序数据快 |
| 缺点 | 效率低 | 不稳定 | 数据量大时慢 |
| 适合场景 | 教学、小数据 | 数据量小 | 数据基本有序 |
记住：这些基础排序算法虽然效率不高，但它们是理解更复杂算法的基础！
六、练习题
练习题1：冒泡排序手动模拟
题目：用手动模拟冒泡排序对数组 [6, 3, 9, 2, 7] 进行排序
要求：写出每一轮比较和交换的过程
答案：
初始：[6, 3, 9, 2, 7]
第1轮：
比较6和3，交换 → [3, 6, 9, 2, 7]
比较6和9，不交换
比较9和2，交换 → [3, 6, 2, 9, 7]
比较9和7，交换 → [3, 6, 2, 7, 9]
第2轮：
比较3和6，不交换
比较6和2，交换 → [3, 2, 6, 7, 9]
比较6和7，不交换
第3轮：
比较3和2，交换 → [2, 3, 6, 7, 9]
第4轮：
比较2和3，不交换
结果：[2, 3, 6, 7, 9]
练习题2：选择排序C#代码填空
题目：补全选择排序代码中的空白
void SelectionSort(int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
int minIndex = ______; // 填空1
for (int j = ______; j < array.Length; j++) // 填空2
{
if (array[j] < array[minIndex])
{
minIndex = ______; // 填空3
}
}
if (minIndex != i)
{
// 交换
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
}
答案：
// 填空1：i
// 填空2：i + 1
// 填空3：j
练习题3：插入排序逻辑判断
题目：对数组 [4, 1, 3, 2] 进行插入排序，回答以下问题：
- 处理第2个元素(1)时，需要向前比较几次？
- 处理第4个元素(2)时，它最终插入到什么位置？
- 整个排序过程中，总共进行了多少次元素移动？
答案：
处理过程：
初始：[4, 1, 3, 2]
第2个元素(1)：
与4比较，4>1，4后移 → [4, 4, 3, 2]
插入1到第1位 → [1, 4, 3, 2] // 比较1次，移动1次
第3个元素(3)：
与4比较，4>3，4后移 → [1, 4, 4, 2]
与1比较，1<3，停止 → 插入3到第2位 → [1, 3, 4, 2] // 比较2次，移动1次
第4个元素(2)：
与4比较，4>2，4后移 → [1, 3, 4, 4]
与3比较，3>2，3后移 → [1, 3, 3, 4]
与1比较，1<2，停止 → 插入2到第2位 → [1, 2, 3, 4] // 比较3次，移动2次
答案：
1. 比较1次
2. 插入到第2位（索引1）
3. 总共移动次数：1 + 1 + 2 = 4次
练习题4：理解冒泡排序过程
题目：观察下面的冒泡排序过程，回答后面的问题
// 对数组 [7, 3, 9, 2, 5] 进行冒泡排序
// 请写出每一轮的结果
初始：[7, 3, 9, 2, 5]
第1轮（比较相邻，大的后移）：
7和3比较 → 交换 → [3, 7, 9, 2, 5]
7和9比较 → 不交换
9和2比较 → 交换 → [3, 7, 2, 9, 5]
9和5比较 → 交换 → [3, 7, 2, 5, 9]
第2轮：
3和7比较 → 不交换
7和2比较 → 交换 → [3, 2, 7, 5, 9]
7和5比较 → 交换 → [3, 2, 5, 7, 9]
（9已排好，不比较）
问题：
1. 第3轮开始时数组是什么？
2. 第3轮需要比较几次？
3. 总共需要多少轮才能完全排好？
答案：
1. 第3轮开始：[3, 2, 5, 7, 9]
2. 第3轮比较：2次（3和2，2和5）
3. 总共需要：4轮（n-1轮，n=5）
练习题5：手动执行选择排序
题目：手动对数组 [8, 3, 6, 1, 4] 执行选择排序，写出每一步
要求：写出每一轮找到的最小值和交换过程
初始：[8, 3, 6, 1, 4]
第1轮：
找最小值：从全部中找，最小值是1（位置3）
交换：8和1交换 → [1, 3, 6, 8, 4]
第2轮：
找最小值：从[3,6,8,4]中找，最小值是3（位置1）
交换：3已在正确位置，不交换 → [1, 3, 6, 8, 4]
第3轮：
找最小值：从[6,8,4]中找，最小值是4（位置4）
交换：6和4交换 → [1, 3, 4, 8, 6]
第4轮：
找最小值：从[8,6]中找，最小值是6（位置4）
交换：8和6交换 → [1, 3, 4, 6, 8]
完成：[1, 3, 4, 6, 8]
1. 关于冒泡排序，以下描述正确的是：
A) 它每次循环将最小的元素移动到正确位置 B) 它的平均时间复杂度是 O(n log n) C) 它是一种不稳定的排序算法 D) 它通过相邻元素比较和交换来排序
答案：D
2. 选择排序的核心思想是：
A) 每次找到未排序部分的最小元素，放到已排序部分的末尾 B) 每次比较相邻元素，将较大的元素向后移动 C) 将每个元素插入到已排序部分的正确位置 D) 通过分治策略将数组分成更小的部分
答案：A
3. 插入排序在哪种情况下性能最好？
A) 数组完全逆序 B) 数组元素全部相同 C) 数组基本有序 D) 数组完全随机
答案：C
4. 顺序查找的时间复杂度是：
A) O(1) B) O(log n) C) O(n) D) O(n²)
答案：C
5. 二分查找的前提条件是：
A) 数组必须使用链表存储 B) 数组必须已经排序 C) 数组元素必须都是正数 D) 数组长度必须是2的幂
答案：B
6. 在冒泡排序中，完成第k轮排序后：
A) 前k个元素已排序 B) 后k个元素已排序 C) 最小的k个元素已排序 D) 最大的k个元素已排序
答案：B
7. 选择排序与冒泡排序的主要区别是：
A) 选择排序更稳定 B) 选择排序交换次数更少 C) 选择排序比较次数更少 D) 选择排序可以在O(n)时间内完成
答案：B
8. 在插入排序中，当处理第i个元素时：
A) 前i-1个元素已经有序 B) 后i-1个元素已经有序 C) 所有元素都未排序 D) 只有第i个元素未排序
答案：A
9. 顺序查找最适合用于：
A) 大型有序数组 B) 小型无序数组 C) 需要频繁插入删除的数据 D) 已经排序的链表
答案：B
10. 二分查找每次比较后：
A) 搜索范围减少一半 B) 搜索范围减少一个元素 C) 搜索范围减少三分之一 D) 搜索范围不变
答案：A
11. 以下哪种排序算法是稳定的？
A) 选择排序 B) 冒泡排序 C) 都不稳定 D) 都稳定
答案：B
12. 在包含n个元素的数组中，顺序查找最坏情况下需要比较：
A) 1次 B) log n次 C) n次 D) n²次
答案：C
13. 二分查找最坏情况下需要比较：
A) 1次 B) log n次 C) n次 D) n²次
答案：B
14. 以下代码实现的是哪种排序？
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
A) 选择排序 B) 插入排序 C) 冒泡排序 D) 快速排序
答案：C
15. 以下代码实现的是哪种排序？
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i-1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
A) 选择排序 B) 插入排序 C) 冒泡排序 D) 归并排序
答案：B
16. 以下代码实现的是哪种查找？
for (int i = 0; i < arr.Length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
A) 顺序查找 B) 二分查找 C) 哈希查找 D) 插值查找
答案：A
17. 以下代码实现的是哪种查找？
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;
A) 顺序查找 B) 二分查找 C) 线性查找 D) 跳转查找
答案：B
18. 对于包含1000个元素的有序数组，二分查找最多需要比较：
A) 10次 B) 100次 C) 500次 D) 1000次
答案：A
19. 哪种排序算法在最好情况下时间复杂度是O(n)？
A) 冒泡排序 B) 选择排序 C) 插入排序 D) 二分查找
答案：C
20. 在二分查找中，当arr[mid] < target时，应该：
A) left = mid B) left = mid + 1 C) right = mid D) right = mid + 1
答案：B
答案解析：
D - 冒泡排序通过相邻元素比较和交换来工作
A - 选择排序每次选择最小元素放到正确位置
C - 插入排序在基本有序的数组上性能最好
C - 顺序查找需要检查每个元素，时间复杂度O(n)
B - 二分查找要求数组必须已排序
B - 冒泡排序每轮将最大的元素"冒泡"到最后
B - 选择排序每轮只交换一次，比冒泡排序交换次数少
A - 插入排序保持前i-1个元素有序
B - 顺序查找简单，适合小型无序数据集
A - 二分查找每次将搜索范围减半
B - 冒泡排序是稳定的，选择排序不稳定
C - 顺序查找最坏情况需要检查所有n个元素
B - 二分查找每次范围减半，时间复杂度O(log n)
C - 这是标准的冒泡排序实现
B - 这是标准的插入排序实现
A - 这是标准的顺序查找实现
B - 这是标准的二分查找实现
A - 2¹⁰=1024>1000，所以最多10次比较
C - 插入排序在最好情况下（已排序数组）是O(n)
B - 目标在右侧，所以左边界设为mid+1
得分参考：
16-20题：优秀！算法理解很扎实
11-15题：良好！掌握了核心概念
6-10题：需要复习一些重要概念
0-5题：建议重新学习这些基础算法
希望这些题目能帮助你巩固所学的算法知识！
C# 中的二分查找法 - 初学者指南
二分查找（Binary Search）是一种高效的查找算法，它比顺序查找快得多，但有一个重要前提：数据必须是有序的。
1. 核心思想：猜数字游戏
想象一下猜数字游戏：我心中想一个1-100之间的数字，你每次猜一个数，我会告诉你"大了"、"小了"还是"对了"。
最聪明的策略：总是猜中间的数！
第一次猜50
如果我说"大了"，你就猜25（1-50的中间）
如果我说"小了"，你就猜75（50-100的中间）
这样每次都能排除一半的可能性！这就是二分查找的核心思想。
2. 算法步骤详解
假设我们在有序数组 [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] 中查找 23：
确定范围：开始时，整个数组都是查找范围
左边界 left = 0（第一个元素）
右边界 right = 9（最后一个元素）
计算中间位置：mid = (0 + 9) / 2 = 4（取整）
中间值 arr[4] = 16
目标值 23 > 16，所以在右半部分继续查找
调整范围：左边界移动到 mid + 1 = 5
新范围：索引 5 到 9
新中间：mid = (5 + 9) / 2 = 7
中间值 arr[7] = 45
目标值 23 < 45，所以在左半部分继续查找
继续查找：右边界移动到 mid - 1 = 6
新范围：索引 5 到 6
新中间：mid = (5 + 6) / 2 = 5
中间值 arr[5] = 23 ← 找到了！
3. C# 代码实现
迭代版本（推荐初学者使用）
using System;
class BinarySearch
{
// 二分查找方法 - 迭代版本
static int BinarySearchIterative(int[] array, int target)
{
int left = 0;
int right = array.Length - 1;
while (left <= right)
{
// 计算中间位置（防止整数溢出）
int mid = left + (right - left) / 2;
Console.WriteLine($"查找范围: [{left}-{right}], 中间位置: {mid}, 值: {array[mid]}");
// 检查中间元素
if (array[mid] == target)
{
return mid; // 找到了！
}
// 如果目标值更大，忽略左半部分
else if (array[mid] < target)
{
left = mid + 1;
Console.WriteLine($" 目标 {target} > {array[mid]}，向右查找");
}
// 如果目标值更小，忽略右半部分
else
{
right = mid - 1;
Console.WriteLine($" 目标 {target} < {array[mid]}，向左查找");
}
}
return -1; // 没找到
}
static void Main()
{
int[] sortedNumbers = { 2, 5, 8, 12, 16, 23, 38, 45, 56, 72 };
int target = 23;
Console.WriteLine("=== 二分查找演示 ===");
Console.WriteLine($"有序数组: [{string.Join(", ", sortedNumbers)}]");
Console.WriteLine($"目标值: {target}");
Console.WriteLine("开始查找...\n");
int result = BinarySearchIterative(sortedNumbers, target);
Console.WriteLine("\n=== 查找结果 ===");
if (result != -1)
{
Console.WriteLine($"找到了！数字 {target} 在索引位置 {result}");
}
else
{
Console.WriteLine($"数字 {target} 不在数组中");
}
}
}
递归版本（了解即可）
// 二分查找方法 - 递归版本
static int BinarySearchRecursive(int[] array, int target, int left, int right)
{
if (left > right)
{
return -1; // 基础情况：没找到
}
int mid = left + (right - left) / 2;
if (array[mid] == target)
{
return mid; // 基础情况：找到了
}
else if (array[mid] < target)
{
// 递归调用：在右半部分查找
return BinarySearchRecursive(array, target, mid + 1, right);
}
else
{
// 递归调用：在左半部分查找
return BinarySearchRecursive(array, target, left, mid - 1);
}
}
// 使用递归版本
int result = BinarySearchRecursive(sortedNumbers, target, 0, sortedNumbers.Length - 1);
4. 完整示例：带详细日志
using System;
class BinarySearchDetailed
{
static void Main()
{
int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25 };
int[] targets = { 7, 20, 25, 0 };
foreach (int target in targets)
{
Console.WriteLine($"\n{'='.PadRight(40, '=')}");
Console.WriteLine($"查找目标值: {target}");
Console.WriteLine($"数组: [{string.Join(", ", numbers)}]");
int result = BinarySearchWithLogging(numbers, target);
if (result != -1)
{
Console.WriteLine($"✅ 成功！目标值 {target} 在索引 {result} 位置");
}
else
{
Console.WriteLine($"❌ 失败！目标值 {target} 不在数组中");
}
}
}
static int BinarySearchWithLogging(int[] array, int target)
{
int left = 0;
int right = array.Length - 1;
int steps = 0;
while (left <= right)
{
steps++;
int mid = left + (right - left) / 2;
Console.WriteLine($"步骤{steps}: 检查范围 [{left}-{right}]，中间索引 {mid}，值 {array[mid]}");
if (array[mid] == target)
{
Console.WriteLine($" 比较: {array[mid]} == {target} ✓");
Console.WriteLine($" 总共用了 {steps} 步查找");
return mid;
}
else if (array[mid] < target)
{
Console.WriteLine($" 比较: {array[mid]} < {target}，向右查找 →");
left = mid + 1;
}
else
{
Console.WriteLine($" 比较: {array[mid]} > {target}，向左查找 ←");
right = mid - 1;
}
}
Console.WriteLine($" 查找结束，总共用了 {steps} 步");
return -1;
}
}
5. 算法特点分析
优点：
✅ 极快：时间复杂度 O(log n)，比顺序查找的 O(n) 快得多
✅ 高效：数据量越大，优势越明显
✅ 简单：逻辑清晰，容易理解
缺点：
❌ 必须有序：要求数据预先排序
❌ 内存连续：通常需要数组这样的连续存储结构
❌ 不适合动态数据：如果数据频繁变动，维护排序的成本高
6. 时间复杂度对比
数据量
顺序查找（最坏）
二分查找（最坏）
10个元素
10次比较
4次比较
100个元素
100次比较
7次比较
1000个元素
1000次比较
10次比较
100万个元素
100万次比较
20次比较
惊人的效率差异：在100万个元素中查找，顺序查找最多需要100万次比较，而二分查找最多只需要20次！
7. 重要细节说明
为什么使用 left + (right - left) / 2？
这是为了防止整数溢出。如果使用 (left + right) / 2，当 left 和 right 都很大时，left + right 可能超过 int 的最大值。
// 安全的方式（推荐）
int mid = left + (right - left) / 2;
// 有风险的方式（不推荐）
int mid = (left + right) / 2; // 可能溢出！
边界条件处理
// 检查数组是否为空
if (array == null || array.Length == 0)
{
return -1;
}
// 检查目标值是否在数组范围内（可选优化）
if (target < array[0] || target > array[array.Length - 1])
{
return -1; // 肯定不在数组中
}
8. 实际应用练习
练习1：查找第一个大于等于目标的值
// 查找第一个大于或等于目标值的元素位置
static int FindFirstGreaterOrEqual(int[] array, int target)
{
int left = 0;
int right = array.Length - 1;
int result = -1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (array[mid] >= target)
{
result = mid; // 记录候选位置
right = mid - 1; // 继续向左找更小的满足条件的位置
}
else
{
left = mid + 1;
}
}
return result; // 返回第一个满足条件的位置，或-1
}
练习2：使用 C# 内置方法
// C# 提供了内置的二分查找方法
int[] numbers = { 1, 3, 5, 7, 9, 11, 13 };
int index = Array.BinarySearch(numbers, 7);
if (index >= 0)
{
Console.WriteLine($"找到在位置 {index}");
}
else
{
Console.WriteLine("未找到");
}
9. 常见错误与调试技巧
常见错误：
忘记排序：对无序数组使用二分查找
边界错误：left <= right 写成 left < right
更新错误：left = mid 而不是 left = mid + 1
调试技巧：
// 添加调试输出
Console.WriteLine($"left={left}, right={right}, mid={mid}, array[mid]={array[mid]}");
// 或者使用调试器设置断点，观察变量变化
总结
二分查找是必须掌握的重要算法：
前提：数据必须有序
核心：每次排除一半的搜索范围
优势：极其高效，特别适合大型数据集
关键：正确处理边界条件和中间值计算
记住：当有人问"这个数据需要排序吗？"，如果要用二分查找，答案就是"必须排序！"
试着运行上面的代码，修改参数来体验二分查找的强大威力吧！