AcWing 789 数的范围 (整数二分)

题目链接：点击查看

题目描述：

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。对于每个查询，返回一个元素 x 的起始位置和终止位置（位置从 00 开始计数）。如果数组中不存在该元素，则返回 

-1 -1

。

输入输出：

输入

6  3

1  2  2  3  3  4

3

4

5

输出

3  4

5  5

-1  -1

题目分析 ：本题即为模拟实现C ++  中的lower_bound() 和 upper_bound() 函数 ，即找出给定一个元素x在数组arr中不大于x的第一个位置 和 不大于x的最后一个位置，当然upper_bound ()函数是在数组中找出大于x的第一个位置，在此基础上减1即可。而后本题所用的基本方法为二分法，要详细分析本题，就不得不说二分法的本质，其本质为对于给定区间D，如果某一种性质可以把此区间分成两部分，那么我们可以通过二分法找到其分界点。二分可以有两种区间划分方式 第一种为D[ l , mid ] ,D[ mid + 1, r]，这一种方式代入到此题的话，最后求得的 l 即为 不大于 x 的第一个位置。第二种划分方式为 D[ l, mid - 1 ] , D[ mid , r ] ,代入到本题，最后的 l 便是求不大于x的最后一个位置。对于两种划分方式 ，我们都有相应的模板。

第一种划分方式模板

int binary_search(int l, int r) {
   int mid = l + r >> 1;
   while ( l < r ) {
     if(arr[mid]是否满足条件)  r = mid;
     else  l = mid + 1;
   }
   return l;
}
           

第二种划分方式模板

int binary_search(int l ,int r) {
    int mid = l + r + 1 >> 1;
    while (l < r) {
       if(arr[mid]是否满足条件) r = mid - 1;
       else l = mid; 
    }
    return l;
}
           

代码 ：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5 + 7;
int n, q;
int arr[N];
int main() {
	scanf("%d %d",&n,&q);
	for(int i = 0; i < n; i ++ ) {
		scanf("%d", &arr[i]); 
	} 
	int l = 0, r = n - 1; 
	while (q -- ) {
		int x;
		scanf("%d", &x);
		int l = 0, r = n - 1; 
		while (l < r) {
		  int mid =  l + r >> 1;
		  if (arr[mid] >= x) r = mid;// 在此while循环中 l最终为不大于所求数x的数的第一个位置 
		  else  l = mid + 1; 
	    }
	    if (arr[l] != x)  
		  printf("-1 -1\n"); 
	    else {
	    	printf("%d ", l);
			int l = 0 , r = n - 1 ;
			while (l < r) {  // 在此while 循环中 l最终为不大于于所求数x的数的最后一个位置 
				int mid = l + r + 1 >> 1; 
				if (arr[mid] > x) r = mid - 1;
				else l = mid;
			} 
			printf("%d\n", l);
		}
	}
	return 0;
}