問題描述

對一個排好序的數組，要求找到大于等于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;}