1、实践题目
改写二分搜索算法 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的值
3、算法描述1 #include2 using namespace std; 3 4 void search(int a[] , int left , int right ,int x, int N){ 5 int i , j , mid, k = 0; //k为标志位，标志是否查找到 6 while(left < right && k == 0){ 7 mid = (left + right)/2 ; 8 9 if(a[mid] == x) {10 11 i = j = mid ;12 cout< <<" "< a[mid]) left = mid + 1 ;19 20 } 21 }22 if(left >= right) {23 24 if(a[left] == x) cout << left <<" "< x) {27 i=-1,j=0;28 cout< <<" "< > n ;43 cin >> x ;44 for(int i = 0 ;i < n; i++){45 cin >> a[i] ;46 }47 48 search(a , 0 ,n-1, x, n) ; //返回下标 49 50 }
#includeusing namespace std;void search(int a[] , int left , int right ,int x){ int i = 0 , j = 0, k = 0; while(left <= right ){ int mid = (left + right)/2 ; if(a[mid] == x) { i = j = mid ; cout< <<" "< a[mid]) left = mid + 1 ; } i = right ; j = left ; cout< <<" "< < > n ; cin >> x ; for(int i = 0 ;i < n; i++){ cin >> a[i] ; } search(a , 0 ,n-1, x) ; }
4、算法时间及空间复杂度分析（要有分析过程）
第一种：时间复杂度： O（n） 由二分搜索的判定树可知，在查找成功时进行比较的关键字个数最多不超过树的深度，即最多为 ⌊log2n⌋ +1 ；若查找失败，比较的关键字个数也不会超过⌊log2n⌋ +1 或者 T（n）= O(1) (n=1) T(n/2) + O(1) (n>1) 时间复杂度为O(log2n)另外，遍历数组元素的时间复杂度为O（n）,因为最坏情况下比较到最后一个元素要比较n-1次所以时间复杂度为O（log2n）+ O(n) = O(n)空间复杂度：没有开辟额外的辅助空间，故为O（1）
第二种：时间复杂度 O（log2n）
5、心得体会
一开始看到这个题目，想着把第一问二分搜索算法复制过去，再加上一个查找所在位置的代码就好。但后来pta出现了几个出错点，甚至出现“运行超时”的错误，仔细检查才发现，由于本题Search函数没有返回值，所以用while循环即使查找成功也不会退出循环，导致运行超时。于是我们设置了标志位k，循环条件加上k == 0，查找成功时设置k=1，这样就解决了这个问题 另外，输出小于x的最大元素位置i和大于x的最小元素位置j，我们用了遍历查找的方法，这里因为没有看清楚题目的输出导致错误后来为了降低时间复杂度，没有再用遍历查找的方法，于是又打了第二份代码，通过发现下标的规律在Search函数里直接输出下标
因为若查找失败，最后都会有right<left ，所以用i = right , j = left 再输出i和j就完成了
要注意的是 查找成功时用exit(0)直接退出，如果没有exit(0)，还会继续执行while后面的代码。