二分查找

• 二分查找
• 分析
• • 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這樣說過二分： 思想很簡單，細節是魔鬼。二分算法常常
一不小心就會寫成死循環。但是一個合格的程式員如果連二分都不會寫，那麼就好
比學數學的不知道拉格朗日中值定理。是以要經常練手二分。