输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。
输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。
输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。
4
1 2 3 4
1
0 2
解题的思路是当left指针指向的下标大于right指针指向的下标时，数组遍历完毕，如果遍历过程中找到了元素就停止遍历，找不到就输出-1.
代码如下：
#include <iostream> using namespace std; int Search(int a[],int x,int n){ int r=n-1, l=0;//定义左右下标 int time=0;//计算比较次数 while(l <= r){ int mid = (r+l) / 2;//中间量 time++; if(x==a[mid]){ cout<<mid<<endl; cout<<time; break; } if(x>a[mid]){ l=mid+1; } else{ r=mid-1; } } if(l>r) { cout<<"-1"<<endl; cout<<time; } return -1; } int main(){ int i, j, mid; int n, x; int a[1000]; cin>>n; for(i=0;i<n;i++){ cin>>a[i]; } cin>>x; Search(a,x,n); return 0; }
7-2 改写二分搜索算法
设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
#include <iostream> #include <cstring> using namespace std; int main(){ int array1[100],i,j,mid,result = 0,number,x; cin >> number;//输入数字个数 cin >> x;//输入目标数 for(i = 0;i < number;i++) cin >> array1[i];//输入数组 int left = 0,right = number - 1;//设左右指针指向数组头尾 if(array1[left] > x) cout << -1 << " " << 0;//x小于全部数的情况 if(array1[right] < x) cout << number - 1 << " " << number;//x大于全部数的情况 for(i = 0;i < number;i++) { mid = left; if(array1[mid] == x) {cout << mid << " " << mid;break;}//x是第一位的情况 mid = right; if(array1[mid] == x) {cout << mid << " " << mid;break;}//x是最后一位的情况 mid = (left + right) / 2; if(array1[mid] == x) {cout << mid << " " << mid;result = 1;break;}//找到x的情况 else if(array1[mid] > x) right = mid; else left = mid; } if(result == 0)//判断result的值，若result仍为0则找不到x { for(i = 1;i < number;i++) if(array1[i] > x && array1[i - 1] < x) cout << i - 1 << " " << i; } }
已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列,的中位数指A?(N−1)/2??的值,即第⌊个数（A?0??为第1个数）。
输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。
在一行中输出两个输入序列的并集序列的中位数。
5
1 3 5 7 9
2 3 4 5 6
4
6
-100 -10 1 1 1 1
-50 0 2 3 4 5
1
第三题要满足符合logN的时间复杂度，在上机的时候没有想到如何解决。回宿舍后在网上看了一下其他大神的代码，暂没有敲出实现的代码...尽量在截止前做出来 原文：https://www.cnblogs.com/KongLeung/p/11572338.html