【数据结构与算法】整数二分

问题描述

对一个排好序的数组，要求找到大于等于7的最小位置和小于等于7的最大位置

大于等于7的最小位置

易知从某个点开始到最右边的边界都满足条件，我们要找到这个区域的最左边的点。

开始二分！
left指针指向最左边界，right指针指向最右边界。
mid = (left + right )/2，指向6
if(check(x[mid]>=7)) right = mid
else left = mid +1
这里6<7，mid指向的元素不符合条件，left 右移至mid + 1
重新计算mid，mid指向9
9>7，满足条件，right 移到mid处，
重新计算mid，mid指向8
8>7，满足条件，right 移到mid处
mid = 8, left = right 停止！

小于等于7的最大位置

易知从左边界到某个点都满足条件，我们要找到这个区域的最右边的点。

eft指针指向最左边界，right指针指向最右边界。
mid = (left + right +1 )/2，指向6
if(check(x[mid]<=7)) left= mid
else right = mid -1

代码

acwing 789 找整数出现的初次和最后一次

#include <iostream>using namespace std;int mat[100001];//找满足条件的最左边界
void findlx(int mat[], int quei, int n){int left = 0;int right = n-1;int mid;while(left!=right){mid = (left +right )>>1;if(mat[mid] >= quei){right = mid;}else {left = mid + 1;}}if(mat[left]!=quei){cout<<-1<<" ";}else{cout<<left<<" ";}}//找满足条件最右边界
void findrx(int mat[], int quei, int n){int left = 0;int right = n-1;int mid;while(left!=right){mid = (right + left +1)>>1;if(mat[mid]<=quei){left = mid;}else{right = mid -1 ;}}if(mat[left]!=quei){cout<<-1<<endl;}else{cout<<left<<endl;}}int main(){int n,q;cin>>n>>q;int i;for(i =0 ; i< n; i++){cin>>mat[i];}for(i =0; i<q; i++){int quei;cin>>quei;int start, end;findlx(mat, quei, n);findrx(mat, quei, n);}return 0;}