搜索技术
1. 二分搜索
如果一些数是有序的，从中找到一个给定的数，可以使用二分搜索策略，每次都和中间的元素作比较，如果比中间的元素小，则在前半部分查找；如果比中间的元素大，则在后半部分查找。这种方法称为二分查找或折半查找，也被称为二分搜索技术。
原理 二分搜索技术
例如，给定有 \(n\) 个元素的序列，这些元素是有序的（假定为升序），从序列中查找元素 \(x\) 。
用一维数组 \(S[]\) 存储该有序序列，设变量 \(low\) 和 \(high\) 表示查找范围的下界和上界，\(middle\) 表示查找范围的中间位置，\(x\) 表示特定的查找元素。
1. 算法步骤
（1）初始化。令 \(low = 0\)，即指向有序数组 \(S[]\) 的第 \(1\) 个元素；\(high = n − 1\)，即指向有序数组 \(S[]\) 的最后一个元素。
（2）判定 \(low \leqslant high\) 是否成立，如果成立，则转向步骤3，否则算法结束。
（3）\(middle = (low + high) / 2\)，即指向查找范围的中间元素。如果数量较大，则为避免 \(low + high\) 溢出，可以采用 \(middle = low + (high - low) / 2\)。
（4）判断 \(x\) 与 \(S[middle]\) 的关系。如果 \(x = S[middle]\)，则搜索成功，算法结束；如果 \(x \ge S[middle]\)，则令 \(low = middle + 1\)；否则令 \(high = middle − 1\)，转向步骤2。
2. 算法实现
用 BinarySearch(int n, int s[], int x) 函数实现二分查找算法，其中 \(n\) 为元素个数，\(s[]\) 为有序数组，\(x\) 为待查找的元素。\(low\) 指向数组的第 \(1\) 个元素，\(high\) 指向数组的最后一个元素。如果 \(low \leqslant high\)，\(middle = (low + high) / 2\)，即指向查找范围的中间元素。如果 \(x = S[middle]\)，则搜索成功，算法结束；如果 \(x > S[middle]\)，则令 \(low = middle + 1\)，在后半部分搜索；否则令 \(high = middle − 1\)，在前半部分搜索。
1. 非递归算法
int BinarySearch(int s[], int n, int x) {//二分查找非递归算法
int low = 0, high = n - 1;//low指向数组的第1个元素，high指向数组的最后一个元素
while (low <= high) {
int middle = (low + high) / 2;//middle为查找范围的中间值
if (x == s[middle])//x等于查找范围的中间值，算法结束
return middle;
else if (x > s[middle])//x大于查找范围的中间元素，在后半部分查找
low = middle + 1;
else//x小于查找范围的中间元素，在前半部分查找
high = middle - 1;
}
return -1;
}
2. 递归算法
递归有自调用问题，增加两个参数 \(low\) 和 \(high\) 标记搜索范围的开始和结束。
int recursionBS(int s[], int x, int low, int high) {//二分查找递归算法
//low指向搜索区间的第1个元素，high指向搜索区间的最后一个元素
if (low > high)//递归结束条件
return -1;
int middle = (low + high) / 2;//计算middle值（查找范围的中间值）
if (x == s[middle])//x等于s[middle]，查找成功，算法结束
return middle;
else if (x < s[middle])//x小于s[middle]，在前部分查找
return recursionBS(s, x, low, middle - 1);
else//x大于s[middle]，在后半部分查找
return recursionBS(s, x, middle + 1, high);
}
4. 算法分析
1. 时间复杂度
如果用 \(T(n)\) 来表示 \(n\) 个有序元素的二分查找算法的时间复杂度，那么结果如下。
-
当 \(n = 1\) 时，需要一次作比较，\(T(n) = O(1)\)。
-
当 \(n > 1\) 时，将待查找元素和中间位置元素作比较，需要 \(O(1)\) 时间，如果比较不成功，那么需要在前半部分或后半部分搜索，问题的规模缩小了一半，时间复杂度变为 \(T(\frac n 2)\)。
- 当 \(n > 1\) 时，可以递推求解如下
递推最终的规模为 \(1\)，零 \(n = 2^x\)，则 \(x = \log n\)。