二分-不止是查找哦

二分过程:首先,假设表中元素是按升序排列,将表中间位置记录的关键字
<https://baike.baidu.com/item/%E5%85%B3%E9%94%AE%E5%AD%97>
与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录
<https://baike.baidu.com/item/%E8%AE%B0%E5%BD%95/1837758>
将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录
<https://baike.baidu.com/item/%E8%AE%B0%E5%BD%95/1837758>
,使查找成功,或直到子表不存在为止,此时查找不成功。(摘自百度百科)

很显然,使用二分查找需要满足两个要求

1.必须采用顺序存储结构
<https://baike.baidu.com/item/%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84>


2.必须按关键字大小有序排列。

 

不断缩小一半的范围,所以时间复杂度O(logn).

贴出有序数组中二分查找的代码
int bsearchWithoutRecursion(int array[],int low,int high,int target) {
while(low<=high) { int mid=low+(high-low)/2; /*使用(low+high)/2会有整数溢出的问题
(问题会出现在当low+high的结果大于表达式结果类型所能表示的最大值时,
这样,产生溢出后再/2是不会产生正确结果的,而low+((high-low)/2) 不存在这个问题*/
if(array[mid]>target)high=mid-1; else if(array[mid]<target)low=mid+1; else
return mid; } return-1; }
一、淘汰一半即可

进一步:二分搜索算法不一定只能在有序数组中进行,只要你在查找的时候发现可以很确定的淘汰数组的一半,留下另一半,那么都是可以用二分搜索的。

来一道水题来说明。

题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。


链接https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路:因为旋转过去的都大于右边的。

设左右端点,中间位置大于右边说明中间位置为旋转过去的,最小值在右边,向右继续查找;

否则说明中间位置为未旋转区域,最小值在左边,向左查找。

 

继续

来看题:

 

本题一般思路:依次查找找到比前后都小的数;或者选出最小数,他肯定是局部最小的;等等

但这些都是O(n)的方法,而用二分可以做到O(logn).

二分思路:

  考虑最左和最右的元素:如果arr[0]<arr[1]  return 0; arr[N-1]<arr[N-2] return N-1;

   考虑最中间元素,如果中间元素大于它左边的元素,那么局部最小值就应该在数组的左半部分

   如果中间元素小于大于它右边的元素,那么局部最小值就应该在数组的右半部分

   中间元素既小于它左边的值又小于它右边的值,那么它就是局部最小

最大化或最小化问题

如果在求解最大最小问题中,能比较简单的判断某个解是否满足条件(这里的简单一般指的是o(n)及以下,视具体数据范围而定),使用二分搜索答案就能很好的解决问题。

举个例子,POJ1064

题目链接:http://poj.org/problem?id=1064 <http://poj.org/problem?id=1064>


题目大意:有n条绳子,长度分别为L[i]。如果从他们中切割出k条长度相同的绳子的话,这k条绳子每条最长能有多长?(答案保留小数点后两位,规定1单位长度的绳子最多可以切割成100份)。

思路:二分搜索答案,每条最短0,最大设置一个较大的数,然后开始二分答案并依次判断,判断也很简单,判断每个绳子的长度整除答案的累加和是不是大于k就好了。

 
#include <cstdio> #include <cmath> using namespace std; const int M=10005;
const double inf=200005.0; double L[M]; int n,k; bool judge(double x)//判断解是否可行
{ int num=0; for(int i=0;i<n;i++)num+=(int)(L[i]/x); return num>=k; } void
solve()//二分答案 { double left=0,right=inf; for(int i=0;i<100;i++) //代替while(r>l)
避免了精度问题 { //1次循环可以把区间缩小一半,100次可以达到10^(-30)的精度 double mid=(left+right)/2;
if(judge(mid)) left=mid; else right=mid; }
printf("%.2f\n",floor(right*100)/100); } int main() {
while(scanf("%d%d",&n,&k)!=-1) { for(int i=0;i<n;i++)scanf("%lf",&L[i]);
solve(); } }
POJ2456

题意:

有n个牛栏,选m个放进牛,相当于一条线段上有 n 个点,选取 m 个点,

使得相邻点之间的最小距离值最大

思路:和上一道题类似,二分答案,判断答案也很简单,贪心即可,遍历,遇到大于枚举的距离就放一只牛,看最后能不能放得下。

代码不贴了

 

最大化平均值

刚开始做这种题的时候,只知道没有按单位价值贪心那么简单,因为物体质量越大它占的比重越大,对总体的影响就越大。单位价值=总价值/总质量,

 

 

 

 

 

 

 

友情链接
KaDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:637538335
关注微信