算法作业之二分查找

//这个。。。。我觉得应该是对的........

 

 

 

设A为n个不同的数排好序的数组，给定数L和U，L<U，问：找到A中所有满足L<x<U的所有的数x。

    算法思想：在A中使用二分查找算法找L。如果L=A[i]，找到L的位置i，然后把i加1；如果L不在A中，那么找到大于L的最小数的位置i。

    类似地，在A中使用二分法算法查找U，找到U所在的位置j，然后j减1；如果U不在A中，那么找到小于U的最大数的位置j。

    最后输出A中从i到j的全体数。

有可能区间没有 比如[12, 12]应该是空  但是我没加...还有输入不规范之类的，也没考虑

 

#include <iostream> using namespace std; int tmp = 1; int n, L, U; int BinarySearch(int A[],int x, int l, int r) { int mid = (l + r) / 2; cout<< x <<" " << l << " " << r << " " << A[mid]<< endl; if (x == A[mid]) return mid+tmp; else if (l == r || l == r-1) { // cout << l << tmp << endl; return (x-A[mid])>0 ? ((l-tmp)<n-1? mid+(tmp+1)/2 : n-1) : 0;//边界情况 找的都是小值 所以左边界... // return (l-tmp)>-1 ? ((l-tmp)<n? mid+(tmp+1)/2 : n-1) : 0;//边界情况 找的都是小值 所以左边界... } return (x > A[mid]) ? BinarySearch(A, x, mid + 1, r) : BinarySearch(A, x, l, mid-1); } int main() { cout << "请输入数组A的元素个数n" << endl; cin >> n; int *A = new int[n]; //读入A cout << "请输入" << n << "个顺序的数组元素:" << endl; for (int i = 0; i < n; i++) cin >> A[i]; while(1){ cout << "请输入L和U"<<endl; cin >> L >> U; tmp = 1; int l = BinarySearch(A, L, 0, n-1); tmp = -1; int r = BinarySearch(A, U, 0, n-1); cout << "l="<<l <<" "<<"r="<< r<<endl; for (int i = l; i <= r; i++) cout << A[i] << " "; cout << endl; } return 0; }