[算法][二分法查找]

             1
            /*
             2
            二分法实验

             3
            1、设a[0:n-1]是一个已排好序的数组.

             4
            请改写二分搜索算法，使得当搜索元素x不在数组中时,

             5
            返回小于x的最大元素的位置I和大于x的最大元素位置j.

             6
            当搜索元素在数组中时，I和j相同，均为x在数组中的位置.

             7
            2、设有n个不同的整数排好序后存放于t[0:n-1]中,

             8
            若存在一个下标I,0<=i<n，使得t[i]=i,

             9
            设计一个有效的算法找到这个下标.

            10
            要求算法在最坏的情况下的计算时间为O(logn).

            11
            */
            12 #include<iostream>
13usingnamespace std;
14/*15功能:1\二分查找改进版
16输入:拍好序的a[],大小n,待查数x,返回参数i,j
17返回:真:找到
18*/19bool BinarySearch(int *a,int n,int x,int& i,int& j){
20int left=0;
21int right=n-1;
22while(left<=right){
23int mid=(left+right)/2;
24if(x==a[mid]){
25             i=j=mid;
26returntrue;
27        }
28if(x>a[mid])
29             left=mid+1;
30else31             right=mid-1;
32    }
33     i=right;
34     j=left;
35returnfalse;
36}
37/*38功能:2\高效查找
39输入:数组,大小,待查值
40返回:下标,若没有返回-1
41*/42int SearchTag(int *a,int n,int x){
43int left=0;
44int right=n-1;
45while(left<=right){
46int mid=(left+right)/2;
47if(x==a[mid]) return mid;
48if(x>a[mid])
49             left=mid+1;
50else51             right=mid-1;
52    }
53return -1;
54}
55int main(){
56int n,i,j,a[1000],x;
57while(cin>>n){//输入数组大小58for(i=0;i<n;i++)cin>>a[i];//输入数据,需要从小到大59         cin>>x;//输入待查数据60         BinarySearch(a,n,x,i,j);//超找61         cout<<"用函数1找到的i,j为: "<<‘(‘<<i<<‘,‘<<j<<‘)‘<<‘\n‘;//输出对应的i,j62         cout<<"用函数2找到的下标为: "<<SearchTag(a,n,x)<<"\n\n";//输出2找到的下标63     }return0;
64 }