二、查找算法
高考考点
查找算法：顺序查找法、二分查找法
一、查找是什么？
查找就是在一堆数据中找特定的东西
比如：
- 在电话本中找某人的号码
- 在字典中找某个字
- 在成绩单中找自己的成绩
二、顺序查找（Sequential Search）
顺序查找法（Sequential Search / Linear Search）是最简单、最基础的查找算法。
1.工作原理
顺序查找法不需要待查找的数据集合提前排序，直接从数据集合的第一个元素开始，逐个将元素与「目标值」进行比对，直到找到匹配的元素，或遍历完整个数据集合仍未找到为止。
比喻：
你在一张无规律排列的购物清单上找「牛奶」，只能从清单的第一行开始，逐行查看，直到找到「牛奶」或翻完整个清单。
2.自然语言描述
以数组 int[] arr = 2 为例，目标是查找值 4，步骤如下：
初始化：从数组的第一个元素（索引 0）开始遍历。
第 1 次比对：索引 0 的元素是 5，与目标值 4 不匹配，继续下一个。
第 2 次比对：索引 1 的元素是 3，与目标值 4 不匹配，继续下一个。
第 3 次比对：索引 2 的元素是 8，与目标值 4 不匹配，继续下一个。
第 4 次比对：索引 3 的元素是 4，与目标值 4 匹配，查找成功，返回当前索引 3。
终止条件：要么找到匹配值返回索引，要么遍历完整个数组（索引到 arr.Length-1）
仍未匹配，返回 -1（约定俗成表示「未找到」）。
3.代码实现(基础版)
using System;
class SequentialSearchExample
{
static void Main()
{
// 待查找的数组
int[] numbers = { 5, 2, 8, 1, 9 };
int target = 8; // 要找的数字
bool found = false; // 是否找到
int position = -1; // 找到的位置（-1表示没找到）
// 顺序查找：从头开始，一个一个检查
for (int i = 0; i < numbers.Length; i++)
{
if (numbers[i] == target)
{
found = true;
position = i; // 记录位置
Console.WriteLine($"✓ 找到了！在第{i+1}个位置");
break; // 找到了就停止
}
else
{
Console.WriteLine($" 不是{target}，继续找...");
}
}
Console.WriteLine($"\n查找结果：{(found ? "找到" : "没找到")}，位置：{position}");
}
}
输出结果：
查找结果：找到，位置：2
4.代码实现(方法版)
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
// 待查找的数组（无序，符合顺序查找的使用场景）
int[] arr = { 5, 3, 8, 4, 2 };
int target = 4; // 要查找的目标值
// 调用顺序查找方法
int resultIndex = SequentialSearch(arr, target);
// 输出结果
if (resultIndex != -1)
{
Console.WriteLine($"目标值 {target} 查找成功，位于数组索引 {resultIndex}");
}
else
{
Console.WriteLine($"目标值 {target} 查找失败，数组中不存在该值");
}
}
static int SequentialSearch(int[] arr, int target)
{
// 健壮性优化：判断数组是否为空或null，避免空引用异常
if (arr == null || arr.Length == 0)
{
Console.WriteLine("数组为空，无法进行查找！");
return -1;
}
// 核心：for循环逐个遍历数组元素，进行比对
for (int i = 0; i < arr.Length; i++)
{
// 找到匹配值，立即返回当前索引（终止查找，提高效率）
if (arr[i] == target)
{
return i;
}
}
// 遍历完整个数组，未找到匹配值，返回-1
return -1;
}
}
运行结果
目标值 4 查找成功，位于数组索引 3
5.代码实现(简化版)
static bool SequentialSearchExists(int[] arr, int target)
{
if (arr == null || arr.Length == 0)
{
return false;
}
// 也可以用foreach遍历，更简洁（无需关注索引）
foreach (int num in arr)
{
if (num == target)
{
return true;
}
}
return false;
}
6.顺序查找特点
- 优点：简单，对数据没有要求（数据可以乱序）
- 缺点：慢，如果数据有10000个，最坏要查10000次
- 时间复杂度：O(n)
三、二分查找（Binary Search）
重要前提：数据必须已排序！
1.工作原理
二分查找法是一种高效的搜索算法，它通过每次排除一半数据的方式，在有序数组中快速找到目标值，就像玩"猜数字"游戏时每次都猜中间值。
形象比喻：猜数字游戏
你心里想一个1-100的数字，别人猜：
- 猜50，你说"太大了"
- 猜25，你说"太小了"
- 每次排除一半的可能性
2.自然语言描述
有序数组：[1, 2, 5, 8, 9] 要找：8
第1步：数组中间是5（位置2），8比5大 → 去右边找 [8, 9]
第2步：右边部分中间是8（位置3），找到了！
3.代码实现
using System;
class BinarySearchExample
{
static void Main()
{
// 1. 定义一个升序排列的整型数组（二分查找的前提：数组必须有序）
int[] arr = { 1, 3, 5, 7, 9 };
// 2. 定义需要查找的目标值
int value = 7;
// 3. 初始化查找范围的左边界（数组起始索引）
int low = 0;
// 4. 初始化查找范围的右边界（数组最后一个元素的索引 = 数组长度-1）
int high = arr.Length - 1;
// 5. 循环查找：只要左边界不超过右边界，说明还有元素可查
while (low <= high)
{
// 6. 计算当前查找范围的中间索引（用low + (high-low)/2 而非 (low+high)/2，避免整数溢出）
int mid = low + (high - low) / 2;
// 7. 核心判断：中间元素等于目标值 → 找到目标
if (arr[mid] == value)
{
// 8. 输出找到的结果（目标值的索引位置）
Console.WriteLine("找到元素，索引为：" + mid);
// 9. 找到后立即退出循环，无需继续查找
break;
}
// 10. 中间元素小于目标值 → 目标值在右半区
else if (arr[mid] < value)
{
// 11. 调整左边界到中间索引的下一位，缩小查找范围到右半区
low = mid + 1;
}
// 12. 中间元素大于目标值 → 目标值在左半区
else
{
// 13. 调整右边界到中间索引的前一位，缩小查找范围到左半区
high = mid - 1;
}
}
// 14. 循环结束后判断：如果左边界超过右边界 → 未找到目标值
if (low > high)
{
// 15. 输出未找到的提示
Console.WriteLine("未找到元素");
}
}
}
输出结果：
查找结果：找到，位置：3
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次比较确定不存在
练习题3：学生成绩查找系统
场景：有一个班级的学生成绩，需要实现查找功能
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}次");
}
}