一, 实践题目: 改写二分搜索算法
二, 问题描述
设 a[0:n-1] 是已排好序的数组, 请改写二分搜索算法, 使得当 x 不在数组中时, 返回小于 x 的最大元素位置 i 和大于 x 的最小元素位置 j. 当搜索元素在数组中时, i 和 j 相同, 均为 x 在数组中的位置.
输入格式:
输入有两行:
第一行是 n 值和 x 值; 第二行是 n 个不相同的整数组成的非降序序列, 每个整数之间以空格分隔.
输出格式:
输出小于 x 的最大元素的最大下标 i 和大于 x 的最小元素的最小下标 j. 当搜索元素在数组中时, i 和 j 相同. 提示: 若 x 小于全部数值, 则输出:-1 0 若 x 大于全部数值, 则输出: n-1 的值 n 的值
输入样例:
在这里给出一组输入. 例如:
6 5 2 4 6 8 10 12
输出样例:
在这里给出相应的输出. 例如:
1 2
三, 算法描述
首先分类讨论 X 是属于以下哪一种情况:
1. 小于所有序列的值
2. 大于所有序列的值
3. 在序列里
4. 不在序列中, 但是序列里分别有最小的大于 X 的数和最大的小于 X 的数
对于 1,2 的情况只需要判断, 然后直接输出
对于 3,4 就需要通过递归的方式不断地折半查找直到找到 X
对于 4 的情况, 笔者设计的算法是在折半查找的途中, 捕捉到是 4 情况的 X
具体代码如下:
- #include<iostream>
- using namespace std;
- int compare(int x, int a[], int left, int right){
- int mid = (right + left) / 2;
- if (a[mid - 1] <x&&x < a[mid])
- cout << mid - 1 << " " << mid;// 在递归途中捕捉, 对应情况 4
- else if (left <= right){
- if (x == a[mid])
- cout << mid << " " << mid;// 对应情况 3
- else if (x < a[mid])
- compare(x, a, left, mid - 1);
- else if (x> a[mid])
- compare(x, a, mid + 1, right);
- }
- }
- int main()
- {
- int n, x;
- int a[1000];
- cin>> n>> x;
- for (int i = 0;i <n;i++)
- cin>> a[i];
- if (x <a[0])
- cout << -1 << " " << 0;// 对应情况 1
- else if (x> a[n - 1])
- cout << n - 1 << " " << n;// 对应情况 2
- else
- compare(x, a, 0, n - 1);
- return 0;
- }
四, 算法时间及空间复杂度
1. 时间复杂度
由于是递归使用二分查找算法, 所以时间复杂度为 O(logn).,
2. 空间复杂度
由于该算法没有临时借用存储空间, 所以空间复杂度为 O(1).
五, 心得体会
一开始笔者用了 for 循环来找到对应 4 情况的 X, 结果发现时间复杂度为 O(n), 于是笔者思考是否可以在二分搜索途中就顺便找出情况 4 的 X 呢? 毕竟二分搜索对应的就是为 O(logn) 的时间复杂度. 最终在多次试验下取得了成功. 这对笔者很有启发, 以后当我们在遇到类似多情况的问题时, 也许我们可以在解决一种情况时顺便解决另一种情况, 既节省了代码量, 又可以保证两种情况共享一种时间复杂度.
来源: http://www.bubuko.com/infodetail-3209229.html