16. 找数

1 描述

给定一个经过升序排序后的数组,以及一个闭区间[a,b]

要求按升序输出给定数组在[a,b]区间内的所有数。

输入描述

第一行为数的个数n

第二行为n个按升序给出的数

第三行两个数a,b 表示区间[a,b]

n范围为[1,1000000]

输入数字范围为[1,1000000000]


输出描述

按升序输出在区间内的数,每行一个数字

如果没有数字在区间内,则输出"No Result!"  (引号去掉)


  测试输入 期待的输出 时间限制 内存限制 额外进程
测试用例 1 以文本方式显示
  1. 5↵
  2. 5 6 7 8 9↵
  3. 4 10↵
以文本方式显示
  1. 5↵
  2. 6↵
  3. 7↵
  4. 8↵
  5. 9↵
1秒 64M 0
测试用例 2 以文本方式显示
  1. 5↵
  2. 5 6 7 8 9↵
  3. 4 4↵
以文本方式显示
  1. No Result!↵
1秒 64M 0
测试用例 3 以文本方式显示
  1. 5↵
  2. 5 6 7 8 9↵
  3. 10 10↵
以文本方式显示
  1. No Result!↵
1秒 64M 0

2 解题

(1)二分法

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

(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;
	//  boundary
	if(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;
	else
		index2 = 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;
	else
		for(i=index1;i<=index2;i++){
			cout<<data[i]<<endl;
			
		}
	
	return 0;
}
  • 小结
  1. a和b分别是需要输出数据的左右边界,使用同一个函数来遍历查找的话需加以处理
    查找匹配b的时候得到的下标对应的data[index2]的值可能是大于b的,不需要输出

if(data[index2]>b){
		index2-=1;
	}
  1. 自定义函数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. 非降序数组
lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个 大于或等于 num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
pper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个 大于 num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
  1. 降序数组,重载lower_bound()和upper_bound()
lower_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
  • 代码
#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;
	else
		index2 = upper_bound(data+index1,data+n,b)-data;

	
	if(data[index2]>b){   //为了方便闭区间输出
		index2-=1;
	}
	if(index2<index1)
		cout<<"No Result!"<<endl;
	else
		for(i=index1;i<=index2;i++){
			cout<<data[i]<<endl;
			
		}
	
	return 0;
}
  • 该函数返回的是地址,减去首地址(数组名)就可以得到下标
  • 有序数组才有意义
上一篇:刷题-力扣-165. 比较版本号


下一篇:移动零