查找算法
顺序查找（Sequence Search）
顺序查找也称线性查找，是一种按照序列原有顺序进行遍历比较的查找算法。
对于任意一个序列以及一个需要查找的元素（关键字），将关键字与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。若某个元素的值与关键字相等，则查找成功；如果直到最后一个元素，元素的值和关键字比较都不等时，则查找不成功。
互动实验
亲手执行顺序查找
访问权限免费
输入目标值，然后按照顺序查找实际比较的先后次序点击数组元素。
输入目标值，然后开始。比较次数: 0
最好的情况就是在第一个位置就找到，算法时间复杂度为 。最坏情况是关键字不存在，需要进行 次比较，时间复杂度为 。
知识测验
题目
对长度为 12 的数组进行顺序查找，目标值不存在。需要比较多少次？
C
typedef int T;
int sequence_search(T *arr, int n, T key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}二分查找（Binary Search）
二分查找法也称折半查找，是一种效率较高的查找方法。折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
知识测验
题目
对数组
[24, 7, 31, 12, 18] 直接使用二分查找，主要问题是什么？
算法思想是假设表中元素是按升序排列，将表中间位置的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
互动实验
亲手执行二分查找
访问权限免费
将每个指针拖到数组元素上。三个指针都正确后，点击 mid 所指元素完成比较。
输入目标值，然后开始。比较次数: 0
二分查找法的时间复杂度为 。
C
typedef int T;
int binary_search(T *arr, int n, T key) {
int start = 0;
int end = n - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}知识测验
题目
升序数组中
array[mid] < target。下一轮应如何更新边界？
动手练习
手工追踪两种查找
给定有序数组 [3, 8, 12, 14, 21, 32, 47, 60]：
- 用顺序查找寻找 32，写出比较序列、下标和比较次数。
- 用二分查找寻找 32，逐轮写出 low、high、mid 和中间值。
- 分别寻找不存在的 13，写出两种算法的比较次数。
- 说明何时即使二分查找更快，你仍会选择顺序查找。