专门做潮搭的网站,静态宠物网站设计论文,新类型 网站,字体设计软件免费二分-不止是查找哦
二分过程#xff1a;首先#xff0c;假设表中元素是按升序排列#xff0c;将表中间位置记录的关键字与查找关键字比较#xff0c;如果两者相等#xff0c;则查找成功#xff1b;否则利用中间位置记录将表分成前、后两个子表#xff0c;如果中间位置记…二分-不止是查找哦
二分过程首先假设表中元素是按升序排列将表中间位置记录的关键字与查找关键字比较如果两者相等则查找成功否则利用中间位置记录将表分成前、后两个子表如果中间位置记录的关键字大于查找关键字则进一步查找前一子表否则进一步查找后一子表。重复以上过程直到找到满足条件的记录使查找成功或直到子表不存在为止此时查找不成功。摘自百度百科
很显然使用二分查找需要满足两个要求
1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。 不断缩小一半的范围所以时间复杂度O(logn).
贴出有序数组中二分查找的代码
int bsearchWithoutRecursion(int array[],int low,int high,int target)
{while(lowhigh){int midlow(high-low)/2;/*使用(lowhigh)/2会有整数溢出的问题问题会出现在当lowhigh的结果大于表达式结果类型所能表示的最大值时这样产生溢出后再/2是不会产生正确结果的而low((high-low)/2)不存在这个问题*/if(array[mid]target)highmid-1;else if(array[mid]target)lowmid1;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?tpId13tqId11159tPage2rp2ru/ta/coding-interviewsqru/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?id1064
题目大意有n条绳子长度分别为L[i]。如果从他们中切割出k条长度相同的绳子的话这k条绳子每条最长能有多长答案保留小数点后两位规定1单位长度的绳子最多可以切割成100份。
思路二分搜索答案每条最短0最大设置一个较大的数然后开始二分答案并依次判断判断也很简单判断每个绳子的长度整除答案的累加和是不是大于k就好了。 #include cstdio
#include cmath
using namespace std;
const int M10005;
const double inf200005.0;
double L[M];
int n,k;
bool judge(double x)//判断解是否可行
{int num0;for(int i0;in;i)num(int)(L[i]/x);return numk;
}
void solve()//二分答案
{double left0,rightinf;for(int i0;i100;i) //代替while(rl) 避免了精度问题{ //1次循环可以把区间缩小一半100次可以达到10^(-30)的精度double mid(leftright)/2;if(judge(mid)) leftmid;else rightmid;}printf(%.2f\n,floor(right*100)/100);
}
int main()
{while(scanf(%d%d,n,k)!-1){for(int i0;in;i)scanf(%lf,L[i]);solve();}
}
POJ2456
题意
有n个牛栏选m个放进牛相当于一条线段上有 n 个点选取 m 个点
使得相邻点之间的最小距离值最大
思路和上一道题类似二分答案判断答案也很简单贪心即可遍历遇到大于枚举的距离就放一只牛看最后能不能放得下。
代码不贴了 最大化平均值
刚开始做这种题的时候只知道没有按单位价值贪心那么简单因为物体质量越大它占的比重越大对总体的影响就越大。单位价值总价值/总质量
