1 描述

2 解题

（1）二分法

• 有序数组中找到与a和b条件符合的下标，瞬间想到了二分法，但是写了一会发现下标的边界处理比较麻烦，然后舍弃了这种方法

（2）直接遍历

• 既然已经是排好序的数组，直接扫描一遍，遇到的时候就返回这个下标
• 代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;long int findindex(long int data[],long int begin,long int key,long int end){for(long int i=0;i<=end;i++){if(data[i]>=key)return i;}
}int main(int argc,char *argv[]){//freopen("file in.txt","r",stdin);long int n;long int *data;	long int index1,index2;long int i;long int a,b;cin>>n;data=(long int*)malloc(sizeof(long int)*n);for(i=0;i<n;i++){  cin>>data[i];}cin>>a>>b;//  boundaryif(a>data[n-1]||b<data[0]||a>b){cout<<"No Result!"<<endl;return 0;}if(a<=data[0])index1=0;else	index1 = findindex(data,0,a,n-1);if(b>=data[n-1])index2=n-1;elseindex2 = findindex(data,index1,b,n-1);//boundary//上面boundary里面的条件语句是考虑一些可以不需要进入遍历函数的情况// 两个边界使用的是同一个函数，实际上他们是有细微区别的while(data[index2+1]==b){index2++;}if(data[index2]>b){index2-=1;}if(index2<index1)cout<<"No Result!"<<endl;elsefor(i=index1;i<=index2;i++){cout<<data[i]<<endl;}return 0;
}

• 小结

1. a和b分别是需要输出数据的左右边界，使用同一个函数来遍历查找的话需加以处理
   查找匹配b的时候得到的下标对应的data[index2]的值可能是大于b的，不需要输出

if(data[index2]>b){index2-=1;}

2. 自定义函数findindex里面遇到第一个大于或者等于key的值就会返回，可能会导致漏掉一些数
   比如这种输入案例

6
5 6 7 8 8 9
4 8

		这样只会输出一个8

• 增加一个处理的语句

while(data[index2+1]==b){index2++;}

• 查找完index1之后查找index2的话并不需要再从头遍历一次，因为经过前面if结构的排除，index2一定在index1的右边（也可能是同一个位置），那么前面的0到index1的部分第一次查找完毕的时候直接扔掉了，符合**减治法**的思想
  
  
  
  

（3）使用lower_bound()和upper_bound()函数

• 头文件 #include<algorithm>
• 相关知识

1. 非降序数组

2. 降序数组,重载lower_bound()和upper_bound()

• 代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;int main(int argc,char *argv[]){// freopen("file in.txt","r",stdin);long int n;long int *data;long int index1,index2;long int i;long int a,b;cin>>n;data=(long int*)malloc(sizeof(long int)*n);for(i=0;i<n;i++){  cin>>data[i];}cin>>a>>b;if(a>data[n-1]||b<data[0]||a>b){cout<<"No Result!"<<endl;return 0;}if(a<=data[0])index1=0;else	index1 = lower_bound(data,data+n,a)-data;// lower_bound()函数返回的是地址if(b>=data[n-1])index2=n-1;elseindex2 = upper_bound(data+index1,data+n,b)-data;if(data[index2]>b){   //为了方便闭区间输出index2-=1;}if(index2<index1)cout<<"No Result!"<<endl;elsefor(i=index1;i<=index2;i++){cout<<data[i]<<endl;}return 0;
}

• 该函数返回的是地址，减去首地址（数组名）就可以得到下标
• 有序数组才有意义