网站建站六个目标,济南企业网站设计,重庆网站制作设计公司,手机php网站开发工具lower_bound算法返回第一个大于等于给定值所在的位置。设置两个指针start和last#xff0c;其中start指向数组的起始位置#xff0c;last指向数组末尾位置之后的位置。当start和last指向相同位置时循环结束。mid指向[start,last)区间的中间位置#xff0c;当中间位置元素值大… lower_bound算法返回第一个大于等于给定值所在的位置。设置两个指针start和last其中start指向数组的起始位置last指向数组末尾位置之后的位置。当start和last指向相同位置时循环结束。mid指向[start,last)区间的中间位置当中间位置元素值大于等于给定val时说明第一个大于等于val值在mid位置的左边更新last为mid。当中间位置元素值小于给定的val时说明第一个大于等于val值在mid右边不包括mid所在的位置。更新start为mid1。
int myLowerBound(vectorint data, int k)
{int start 0;int last data.size();while (start last){int mid (start last) / 2;if (k data[mid]) start mid 1;else last mid;}return start;
}upper_bound算法返回第一个大于给定元素值所在的位置设置两个指针start和last其中start指向数组的起始位置last指向数组末尾位置之后的位置当start和last指向相同位置时循环结束mid指向[start,last)区间的中间位置当中间位置元素值小于等于给定val时说明第一个大于val值在mid位置的右边更新start为mid1。当中间位置元素值大于给定元素时说明第一大于在mid左边包括mid所在位置所以更新last为mid。
int myUpperBound(vectorint data, int k)
{int start 0;int last data.size();while (start last){int mid (start last) / 2;if (k data[mid]) start mid 1;else last mid;}return start;
}以上都是左端是满足值。特点就是都是l永远都是mid1r永远都是mid
下面再来一发右端是满足值的至于是lower还是upper就看ok函数中加不加等号就可以了找一个特例比如只有两个值的模拟一下 while(lr) {m(lr1)/2;if(ok()) lm;else rm-1;}printf(l %d\n,l); 等价于左端满足值的就是在else中ansm就可以了比较好实现 while(lr) {m(lr)/2;if(ok()) lm1,ansm;else rm-1;}printf(ans %d\n,ans);
关于binarysearch https://blog.csdn.net/daniel_ustc/article/details/17307937
upper_bound再来一种实现
int Search(int num,int low,int high)
{int mid;while(lowhigh){mid(lowhigh)/2;if(numb[mid]) lowmid1;else highmid-1;} return low;
}
纪念编辑时间2018.10.08 10:12:42
