个人网站备案 流程,帮忙做快站旅游网站,WordPress抓取豆瓣,安庆市建设银行网站首页这道题就是一道简单的模板题#xff0c;我们分析一下#xff01;#xff0c;首先我们要找大于等于x的起始位置 我们还是用两个指针#xff0c;left指向1#xff0c;right指向n#xff0c;如果a[mid]x left mid1
如果a[mid]x 就让right mid
如果数组全是小于x… 这道题就是一道简单的模板题我们分析一下首先我们要找大于等于x的起始位置 我们还是用两个指针left指向1right指向n如果a[mid]x left mid1
如果a[mid]x 就让right mid
如果数组全是小于x的话x 3 ,[0 , 1 , 2] 我们最后就会指向22还是小于x的所以我们这个数组大于等于x的值不存在返回0
接下来我们找一下小于等于y的终止位置 如果a[mid]大于yrightmid-1
如果a[mid]小于等于yleftmid1
我们还需要考虑一下最后结果可能是大于y的情况比如y是3数组是[4,5,6]的话结果是44还是大于3的根本就找不到小于等于3的区间所以返回0
好的话不多说我们写一下代码
#include iostream
using namespace std;
const int N 1e5 10;
int n;
int a[N];
int binary_search(int x1, int x2)
{int left 1, right n;while (left right){int mid (left right) / 2;if (a[mid] x1) right mid;else left mid 1;}if (a[left] x1) return 0;int tmp left;left 1, right n;while (left right){int mid (left right 1) / 2;if (a[mid] x2) left mid;else right mid - 1;}if(a[left]x2) return 0;return left - tmp 1;
}
int x, y;
int main()
{cin n;for (int i 1; i n; i) cin a[i];int q; cin q;while (q--){cin x y;cout binary_search(x, y) endl;}
}
