二分查找

• 二分查找
• 分析
• • p1010
  • p1044
  • p1048
  • p1085
• 小结

二分查找

1010. Radix (25)-PAT甲级真题（二分法）

1044. Shopping in Mars (25)-PAT甲级真题（二分查找）

1048. Find Coins (25)-PAT甲级真题(二分|Hash散列)

1085. Perfect Sequence (25)-PAT甲级真题

分析

pat上二分查找一共4道题， 4道题出的都挺不错。pat上二分查找，为难你的地方：
1， 知道什么时候使用二分， 查找的场景下。
2， 单调序列，没有明确给你， 如p1010, p1044。需要你自己发现制造单调序列
3，结合具体场景灵活选用 以下二分的某一种：
		3.1  binarySearch(int nums[], int n, int x)
		3.2 left_bound(int nums[], int n, int x): p1044, p1048, p1010
		3.3 right_bound(int nums[], int n, int x): p1085
可以看到， 常考3.2
3.2和3.3区别 如 1,3,3,3,6   x=3,   3.2返回索引1， 3.3返回索引4。
晴神笔记上更加通俗易懂， 3.2返回的是第一个大于等于x的位置， 如x=-1, 
将返回0， 一种理解是大于等于-1的第一个位置。
另外一种理解，使用左闭右开的区间[0,0), 这样表示小于x的元素个数是0。
注意3.2中有些题我们需要判断边界情况下返回索引指向关键字是否等于x，
 或者判断存不存在？如7， 那么返回索引5， 这种情况下表示大于等于x的数字
 不存在。或者理解成[0,5), 小于7的关键字有5个。
 
难度： p1010 > p1044 > p1085 > p1048
           

p1010

题目大意： 给你两个数， 其中一个数已知，求让这两个数相等的另外一个数的进制。
如果不存在，那么返回Impossible.
分析： 本题有20个测试样例， 并且pat上通过率最低，仅仅0.11。
注意： 
	1,首先不要使用 binarySearch，为什么？ 因为 如 2， 2， 1， 10这种， 正确
	答案是3以上都可，但是题目要求最小。所以要是用左边界，
	条件：[x,mid] < [a, r] 说明正确答案在 left右侧，=> left=mid+1  
			   [x,mid]>[a,r]  说明你正确答案在right左侧， => right =mid
			   [x,mid]==[a,r] => right[mid]

	以为这样就行了吗？如何初始化 left和right？
	要求的进制下限 是 数字串最大数字加1， 上限是已知数10进制下数字加1.
	爆long long怎么办？
	[x,mid]<0说明爆long long了， 因为两个正数相加溢出为负。 => right=mid即可

	本题可以做的原因就是满足[x,mid]>=[a,r]的最小mid没有爆long long。
	不存在的话条件：[x,mid]>[a,r]
	从这个问题可以看到 单调序列不是显示给出的.
           

p1044

题目大意：求一串的数字中连续的一段，使得这个连续的段内数字的和恰好等于所期
望的值m。如果不能找到恰好等于，就找让自己付出最少的价格（总和必须大于等于
所给值）的那段区间，求所有可能的结果～

分析： 这个单调序列，我一开始没找到， 用了暴力循环， 对了3个测试样例。
单调序列是 sum[i] ,  sum[k]-sum[i-1]就是 一段子序列和， 假设当前处理数字串位置i,	
要查找的数字是x = sum[i-1]+m 。
	之后使用左边界函数处理就水到渠成了。

非常好的一道题。
           

p1048

题目大意：给出n个正整数和一个正整数m，问n个数字中是否存在一对数字a和b
(a <= b),使a+b=m成立。如果有多个，输出a最小的那一对。

分析： 可以使用哈希， 也可以使用，要注意 [1,3,3,3,6]  或者[1,3,6] m=6, 这种， 
哈希可以定义个cnt数组， 避免a和b在同一个位置。 二分的话，使用左边界函数找到
第一个大于等于（m-a）的数字b， 如果b+a==m且b与a不在一个位置，就是正确
答案。如果b+a==m但是b和a在同一个位置， 找b的下一个数c, 判断c+a==m即可。
           

p1085

题目大意：给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是
m，如果M <= m * p，则称这个数列是完美数列。现在给定参数p和一些正整数，请你
从中选择尽可能多的数构成一个完美数列。输入第一行给出两个正整数N（输入正数的
个数）和p（给定的参数），第二行给出N个正整数。在一行中输出最多可以选择多少
个数可以用它们组成一个完美数列

分析：简单题。首先将数列从小到大排序，设当前结果为result = 0，当前最长长度为
temp = 0；从i = 0～n，j从i + result到n，【因为是为了找最大的result，所以下一次
j只要从i的result个后面开始找就行了】每次计算temp若大于result则更新result，
最后输出result的值～(摘自柳神）

	和p1044风格差不多， 这里使用哪个函数， 如1,3,3,3,6， p=3， 那么对于1来说
1,3,3,3都符合， 若是3的左边界，那么漏了3个， 明显这里返回3的右边界为好。
利用第二种思想解释， 作差就是满足条件的数字个数。
           

小结

KMP算法创立者之一Knuth这样说过二分： 思想很简单，细节是魔鬼。二分算法常常
一不小心就会写成死循环。但是一个合格的程序员如果连二分都不会写，那么就好
比学数学的不知道拉格朗日中值定理。所以要经常练手二分。