两种查找算法：顺序查找 vs 二分查找（一看就懂）
一、查找是什么？
查找就是在一堆数据中找特定的东西
比如：
- 在电话本中找某人的号码
- 在字典中找某个字
- 在成绩单中找自己的成绩
二、顺序查找（Sequential Search）
形象比喻：挨家挨户找人
就像警察找人，从第一户开始敲门问："请问XX在家吗？"
查找过程动画（脑补）：
数组：[5, 2, 8, 1, 9]
要找：8
第1步：检查第1个元素5，不是8
第2步：检查第2个元素2，不是8
第3步：检查第3个元素8，找到了！
C#代码（带详细注释）：
using System;
class SequentialSearchExample
{
static void Main()
{
// 待查找的数组
int[] numbers = { 5, 2, 8, 1, 9 };
int target = 8; // 要找的数字
Console.WriteLine($"在数组 [{string.Join(", ", numbers)}] 中查找 {target}");
Console.WriteLine("使用顺序查找（一个一个找）\n");
bool found = false; // 是否找到
int position = -1; // 找到的位置（-1表示没找到）
// 顺序查找：从头开始，一个一个检查
for (int i = 0; i < numbers.Length; i++)
{
Console.WriteLine($"检查第{i+1}个元素：{numbers[i]}");
if (numbers[i] == target)
{
found = true;
position = i; // 记录位置
Console.WriteLine($"✓ 找到了！在第{i+1}个位置");
break; // 找到了就停止
}
else
{
Console.WriteLine($" 不是{target}，继续找...");
}
}
if (!found)
{
Console.WriteLine($"✗ 没找到 {target}");
}
Console.WriteLine($"\n查找结果：{(found ? "找到" : "没找到")}，位置：{position}");
}
}
输出结果：
在数组 [5, 2, 8, 1, 9] 中查找 8
使用顺序查找（一个一个找）
检查第1个元素：5
不是8，继续找...
检查第2个元素：2
不是8，继续找...
检查第3个元素：8
✓ 找到了！在第3个位置
查找结果：找到，位置：2
顺序查找特点：
- 优点：简单，对数据没有要求（数据可以乱序）
- 缺点：慢，如果数据有10000个，最坏要查10000次
- 时间复杂度：O(n)
三、二分查找（Binary Search）
重要前提：数据必须已排序！
形象比喻：猜数字游戏
你心里想一个1-100的数字，别人猜：
- 猜50，你说"太大了"
- 猜25，你说"太小了"
- 每次排除一半的可能性
查找过程动画（脑补）：
有序数组：[1, 2, 5, 8, 9]
要找：8
第1步：数组中间是5（位置2），8比5大 → 去右边找 [8, 9]
第2步：右边部分中间是8（位置3），找到了！
C#代码（带详细注释）：
using System;
class BinarySearchExample
{
static void Main()
{
// 注意：二分查找要求数组必须已排序！
int[] numbers = { 1, 2, 5, 8, 9 }; // 已经排好序
int target = 8; // 要找的数字
Console.WriteLine($"在有序数组 [{string.Join(", ", numbers)}] 中查找 {target}");
Console.WriteLine("使用二分查找（每次排除一半）\n");
// 二分查找的三个关键指针
int left = 0; // 查找范围的左边界
int right = numbers.Length - 1; // 查找范围的右边界
bool found = false; // 是否找到
int position = -1; // 找到的位置
int step = 1; // 记录第几步
while (left <= right) // 只要查找范围有效
{
// 计算中间位置
int mid = (left + right) / 2;
int midValue = numbers[mid];
Console.WriteLine($"第{step}步：");
Console.WriteLine($" 查找范围：下标{left}到{right} → [{string.Join(", ", numbers[left..(right+1)])}]");
Console.WriteLine($" 中间位置：下标{mid}，值是{midValue}");
if (midValue == target)
{
// 找到了！
found = true;
position = mid;
Console.WriteLine($" ✓ 找到了！在位置{mid}");
break;
}
else if (midValue < target)
{
// 目标比中间值大，去右边找
Console.WriteLine($" {target} > {midValue}，去右边找");
left = mid + 1;
}
else
{
// 目标比中间值小，去左边找
Console.WriteLine($" {target} < {midValue}，去左边找");
right = mid - 1;
}
step++;
Console.WriteLine();
}
if (!found)
{
Console.WriteLine($"✗ 没找到 {target}");
}
Console.WriteLine($"\n查找结果：{(found ? "找到" : "没找到")}，位置：{position}");
Console.WriteLine($"总共查找了{step-1}次");
// 对比：如果是顺序查找这个数组
Console.WriteLine("\n【对比】如果是顺序查找：");
for (int i = 0; i < numbers.Length; i++)
{
if (numbers[i] == target)
{
Console.WriteLine($"需要查找{i+1}次才能找到");
break;
}
}
}
}
输出结果：
在有序数组 [1, 2, 5, 8, 9] 中查找 8
使用二分查找（每次排除一半）
第1步：
查找范围：下标0到4 → [1, 2, 5, 8, 9]
中间位置：下标2，值是5
8 > 5，去右边找
第2步：
查找范围：下标3到4 → [8, 9]
中间位置：下标3，值是8
✓ 找到了！在位置3
查找结果：找到，位置：3
总共查找了2次
【对比】如果是顺序查找：需要查找4次才能找到
二分查找特点：
- 优点：非常快！100万数据最多查20次
- 缺点：要求数据必须已排序
- 时间复杂度：O(log n)
四、两种查找算法对比
| 特性 | 顺序查找 | 二分查找 |
|---|---|---|
| 数据要求 | 任意顺序 | 必须已排序 |
| 查找方式 | 从头到尾一个一个找 | 每次排除一半 |
| 最坏情况 | 找n次 | 找log₂n次 |
| 1000个数据 | 最多找1000次 | 最多找10次 |
| 100万个数据 | 最多找100万次 | 最多找20次 |
| 代码难度 | 简单 | 稍复杂 |
| 适用场景 | 数据少、不常查找 | 数据多、经常查找 |
五、重要概念：时间复杂度
查找次数的增长对比：
数据量(n) 顺序查找(最多) 二分查找(最多)
----------------------------------------
10 10次 4次
100 100次 7次
1000 1000次 10次
10000 10000次 14次
100000 100000次 17次
1000000 1000000次 20次
二分查找的速度优势随着数据量增大而明显！
六、练习题
练习题1：顺序查找代码填空
题目：补全顺序查找代码中的空白
int SequentialSearch(int[] array, int target)
{
for (int i = 0; i < ______; i++) // 填空1
{
if (array[i] == ______) // 填空2
{
return ______; // 填空3：找到了，返回位置
}
}
return ______; // 填空4：没找到，返回-1
}
答案：
// 填空1：array.Length
// 填空2：target
// 填空3：i
// 填空4：-1
练习题2：二分查找逻辑判断
题目：在有序数组 [2, 4, 6, 8, 10, 12, 14, 16, 18, 20] 中查找数字 14，回答以下问题：
- 第一次比较的中间位置是哪个数？
- 需要几次比较才能找到？
- 如果查找数字
5，需要几次比较才能确定不存在？
手动查找过程：
数组：[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
找：14
第1次：中间是下标4(10)，14>10 → 去右边 [12,14,16,18,20]
第2次：右边中间是下标7(16)，14<16 → 去左边 [12,14]
第3次：左边中间是下标5(12)，14>12 → 去右边 [14]
第4次：找到14
答案：
1. 第一次比较的数：10
2. 找到14需要：4次比较
3. 找5的过程：
第1次：中间10，5<10 → 去左边 [2,4,6,8]
第2次：中间6，5<6 → 去左边 [2,4]
第3次：中间4，5>4 → 去右边 []（右边为空）
总共：3次比较确定不存在
七、排序算法练习题（巩固算法思路）
排序练习题1：理解冒泡排序过程
题目：观察下面的冒泡排序过程，回答后面的问题
// 对数组 [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）
排序练习题2：手动执行选择排序
题目：手动对数组 [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]
八、综合应用题
应用题：学生成绩查找系统
场景：有一个班级的学生成绩，需要实现查找功能
using System;
class StudentGradeSystem
{
static void Main()
{
// 学生成绩（无序）
int[] grades = { 85, 42, 90, 58, 76, 95, 33 };
Console.WriteLine("学生成绩系统");
Console.WriteLine("成绩列表：" + string.Join(", ", grades));
while (true)
{
Console.Write("\n请输入要查找的成绩（输入-1退出）：");
string input = Console.ReadLine();
if (!int.TryParse(input, out int target) || target == -1)
break;
Console.WriteLine("\n=== 方法1：顺序查找（无序时用）===");
SequentialSearchDemo(grades, target);
Console.WriteLine("\n=== 方法2：二分查找（需要先排序）===");
BinarySearchDemo(grades, target);
}
}
static void SequentialSearchDemo(int[] array, int target)
{
int count = 0; // 查找次数
for (int i = 0; i < array.Length; i++)
{
count++;
if (array[i] == target)
{
Console.WriteLine($"找到了！位置：{i}，查找了{count}次");
return;
}
}
Console.WriteLine($"没找到！查找了{count}次");
}
static void BinarySearchDemo(int[] array, int target)
{
// 二分查找需要先排序
int[] sortedArray = new int[array.Length];
Array.Copy(array, sortedArray, array.Length);
Array.Sort(sortedArray);
Console.WriteLine("先排序数组：" + string.Join(", ", sortedArray));
int left = 0;
int right = sortedArray.Length - 1;
int count = 0;
while (left <= right)
{
count++;
int mid = (left + right) / 2;
if (sortedArray[mid] == target)
{
Console.WriteLine($"找到了！在排序后位置：{mid}，查找了{count}次");
Console.WriteLine("（注意：这是排序后的位置，不是原位置）");
return;
}
else if (sortedArray[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
Console.WriteLine($"没找到！查找了{count}次");
}
}
九、学习建议
- 先理解思想，再写代码：明白"为什么"比记住"怎么写"更重要
- 画图辅助理解：在纸上画数组，模拟查找过程
- 对比学习：两种查找算法对比着学
- 注意前提条件：二分查找必须数据有序！
- 思考应用场景：什么时候用顺序查找？什么时候用二分查找？
十、一句话总结
顺序查找：简单但慢，适合数据少或无序数据
二分查找：快但需要先排序，适合数据多且经常查找
关键区别：二分查找每次排除一半，效率远高于顺序查找！