二分查找問題全集

1、二分查找問題全集1，原始二分查找題目：給定一個有序（非降序）數(shù)組A，求任意一個i使得Ai等于target，不存在則返回-1例如：2,4,6,8,9找(4) 位置11.1 遞歸版cpp view plain copyprint?1. int bSearch(int a, int low, int high, int target)  2.     if(low > high)  3.   &#

2、160;     return -1;  4.     int mid = (low + high)/2;  5.     if(target<amid)  6.         return bSearch(a,low,mid-1,target);&#

3、160; 7.     else if(target>amid)  8.         return bSearch(a,mid+1,high,target);  9.     /if(target = amid)  10.     return mid; &#

4、160;11.   int bSearch(int a, int low, int high, int target)if(low > high)return -1;int mid = (low + high)/2;if(target<amid)return bSearch(a,low,mid-1,target);else if(target>amid)return bSearch(a,mid+1,high,target);/if(target = amid)return mid;1.2 迭代版cpp view plain copyprint?1. int

5、 search(int A, int n, int target)  2.   3.     int low = 0, high = n-1;  4.     while(low <= high)  5.       6.  

6、;       / 注意：若使用(low+high)/2求中間位置容易溢出  7.         int mid = low+(high-low)>>1);   8.         if(Amid = target)  9.

7、             return mid;  10.         else if(Amid < target)  11.             low = mid

8、+1;  12.         else / Amid > target  13.             high = mid-1;  14.       15.     

9、;return -1;  16.   int search(int A, int n, int target)int low = 0, high = n-1;while(low <= high)/ 注意：若使用(low+high)/2求中間位置容易溢出int mid = low+(high-low)>>1); if(Amid = target)return mid;else if(Amid < target)low = mid+1;else / Amid > targethigh = mid-1;return -1

10、;1.3 返回插入位置給定一個有序（非降序）數(shù)組A，若target在數(shù)組中出現(xiàn)，返回位置，若不存在，返回它應(yīng)該插入的位置。cpp view plain copyprint?1. int search(int A, int n, int target)  2.   3.     int low = 0, high = n-1;  4.    

11、0;while(low <= high)  5.       6.         / 注意：若使用(low+high)/2求中間位置容易溢出  7.         int mid = low+(high-low)>>1);   

12、8.         if(Amid = target)  9.             return mid;  10.         else if(Amid < target)  11.

13、             low = mid+1;  12.         else / Amid > target  13.             high 

14、= mid-1;  14.       15.     return -(low+1);  16.   int search(int A, int n, int target)int low = 0, high = n-1;while(low <= high)/ 注意：若使用(low+high)/2求中間位置容易溢出int mid = low+(high-low)>>1); if(Amid = ta

15、rget)return mid;else if(Amid < target)low = mid+1;else / Amid > targethigh = mid-1;return -(low+1);之所以返回-（low+1）而不是直接返回-low是因為low可能為0，如果直接返回-low就無法判斷是正常返回位置0還是查找不成功返回的0。 2，含重復(fù)元素，求=target的最小一個問題：給定一個有序（非降序）數(shù)組A，可含有重復(fù)元素，求最小的i使得Ai等于target，不存在則返回-1例如：A2,4,6,8,8,8,9求8得最小位置3cpp view plain copyprint?1

16、. int search(int A, int n, int target)  2.   3.     int low = 0, high = n-1;  4.     while(low <= high)         

17、          5.       6.         / 注意：若使用(low+high)/2求中間位置容易溢出  7.         int mid = low+(high-low)>>1);

18、60;  8.         if(Amid = target)  9.           10.             if(mid > 0 && Amid-1 

19、;= target)  11.                 high = mid-1;             12.            &#

20、160;else   13.                 return mid;  14.           15.         else if(Amid <

21、60;target)  16.             low = mid+1;               17.         else / Amid > t

22、arget  18.             high = mid-1;             19.       20.     return -(low+1);   

23、; 21.   int search(int A, int n, int target)int low = 0, high = n-1;while(low <= high) / 注意：若使用(low+high)/2求中間位置容易溢出int mid = low+(high-low)>>1); if(Amid = target)if(mid > 0 && Amid-1 = target)high = mid-1; else return mid;else if(Amid < target)low = mid+1; else

24、 / Amid > targethigh = mid-1; return -(low+1); 3，含重復(fù)元素，求=target的最大一個問題：給定一個有序（非降序）數(shù)組A，可含有重復(fù)元素，求最大的i使得Ai等于target，不存在則返回-1例如：A2,4,6,8,8,8,9求8得最大位置5cpp view plain copyprint?1. int search(int A, int n, int target)  2.   3.     int&

25、#160;low = 0, high = n-1;  4.     while(low <= high)                   5.       6.     

26、    / 注意：若使用(low+high)/2求中間位置容易溢出  7.         int mid = low+(high-low)>>1);   8.         if(Amid = target)  9.    

27、       10.             if(mid < n-1 && Amid+1 = target)  11.                

28、60;low = mid+1;             12.             else   13.                 

29、;return mid;  14.           15.         else if(Amid < target)  16.             low = mid+1; 

30、;              17.         else / Amid > target  18.             high = mid-1; 

31、60;           19.       20.     return -(low+1);    21.   int search(int A, int n, int target)int low = 0, high = n-1;while(low <= high) / 注意：若使用(low+high)/2

32、求中間位置容易溢出int mid = low+(high-low)>>1); if(Amid = target)if(mid < n-1 && Amid+1 = target)low = mid+1; else return mid;else if(Amid < target)low = mid+1; else / Amid > targethigh = mid-1; return -(low+1); 4，含重復(fù)元素，求<target的最大一個問題：給定一個有序（非降序）數(shù)組A，可含有重復(fù)元素，求最大的i使得Ai小于target，不存在則返回

33、-1例如：A2,4,6,8,8,8,9求9得最大位置5問題轉(zhuǎn)化：含重復(fù)元素，求2【=target的最小一個】的前一個。cpp view plain copyprint?1. int search(int A, int n, int target)  2.   3.     int low = 0, high = n-1;  4.     

34、while(low <= high)                   5.       6.         / 注意：若使用(low+high)/2求中間位置容易溢出  7.   

35、0;     int mid = low+(high-low)>>1);   8.         if(Amid = target)  9.           10.        &

36、#160;    if(mid > 0 && Amid-1 = target)  11.                 high = mid-1;           

37、;  12.             else   13.                 return (mid=0)?-1:mid-1;  14.        &#

38、160;  15.         else if(Amid < target)  16.             low = mid+1;             

39、0; 17.         else / Amid > target  18.             high = mid-1;             19. 

40、0;     20.     return -(low+1);    21.   int search(int A, int n, int target)int low = 0, high = n-1;while(low <= high) / 注意：若使用(low+high)/2求中間位置容易溢出int mid = low+(high-low)>>1); if(Amid = target)if(mid > 0 &

41、amp;& Amid-1 = target)high = mid-1; else return (mid=0)?-1:mid-1;else if(Amid < target)low = mid+1; else / Amid > targethigh = mid-1; return -(low+1); 5，含重復(fù)元素，求>target的最小一個問題：給定一個有序（非降序）數(shù)組A，可含有重復(fù)元素，求最小的i使得Ai大于target，不存在則返回-1例如：A2,4,6,8,8,8,9求6的最小位置3問題轉(zhuǎn)化：含重復(fù)元素，求3【=target的最大一個】的后一個。cpp vi

42、ew plain copyprint?1. int search(int A, int n, int target)  2.   3.     int low = 0, high = n-1;  4.     while(low <= high)     

43、0;             5.       6.         / 注意：若使用(low+high)/2求中間位置容易溢出  7.         int mid = low+(hig

44、h-low)>>1);   8.         if(Amid = target)  9.           10.             if(mid < n-1 &

45、& Amid+1 = target)  11.                 low = mid+1;             12.         

46、;    else   13.                 return (mid=n-1)?-n:mid+1;  14.           15.        

47、 else if(Amid < target)  16.             low = mid+1;               17.         el

48、se / Amid > target  18.             high = mid-1;             19.       20.     re

49、turn -(low+1);    21.   int search(int A, int n, int target)int low = 0, high = n-1;while(low <= high) / 注意：若使用(low+high)/2求中間位置容易溢出int mid = low+(high-low)>>1); if(Amid = target)if(mid < n-1 && Amid+1 = target)low = mid+1; else return (mid=n-1)

50、?-n:mid+1;else if(Amid < target)low = mid+1; else / Amid > targethigh = mid-1; return -(low+1); 6，含重復(fù)元素，求=target的出現(xiàn)次數(shù)問題：給定一個有序（非降序）數(shù)組A，可含有重復(fù)元素，求target在數(shù)組中出現(xiàn)的次數(shù)。例如：A2,4,6,8,8,8,9求8的出現(xiàn)次數(shù)3求出第一次出現(xiàn)位置和最后一次出現(xiàn)位置。由于前面都已實現(xiàn)，這里不多解釋。請參考實現(xiàn)代碼與注釋cpp view plain copyprint?1. int count(int A, int&

51、#160;n, int target)  2.   3.     int firstPos = searchFirstPos(A, n, target); / 第一次出現(xiàn)位置  4.     if(firstPos = -1)  5.         

52、;return 0;  6.     int lastPos = searchLastPos(A, n, target);  / 最后一次出現(xiàn)位置  7.     return lastPos-firstPos+1;  / 出現(xiàn)次數(shù)  8.   int count(int A, int n, int targ

53、et)int firstPos = searchFirstPos(A, n, target); / 第一次出現(xiàn)位置if(firstPos = -1)return 0;int lastPos = searchLastPos(A, n, target); / 最后一次出現(xiàn)位置return lastPos-firstPos+1; / 出現(xiàn)次數(shù)7，含重復(fù)元素，求絕對值最小的元素問題：給定一個有序（非降序）數(shù)組A，可含有重復(fù)元素，求絕對值最小的元素的位置例如：A-4,-2,-1,2,3,8,9求結(jié)果為2cpp view plain copyprint?1. int searchMinAbs(i

54、nt A, int n)  2.   3.     int low = 0, high = n-1;  4.     while(low < high)  5.       6.        

55、 int mid = low+(high-low)>>1);  7.         if(Amid < 0)  8.             low = mid+1;  9.      &#

56、160;  else / Amid >= 0  10.             high = mid;  11.       12.     /* 循環(huán)結(jié)束時，如果low != n-1，Alow >=

57、0;0，如果low>0，Alow-1 < 0 */  13.     if(low > 0 && abs(Alow-1) < abs(Alow)  14.         return low-1;  15.     else &

58、#160;16.         return low;  17.   int searchMinAbs(int A, int n)int low = 0, high = n-1;while(low < high)int mid = low+(high-low)>>1);if(Amid < 0)low = mid+1;else / Amid >= 0high = mid;/* 循環(huán)結(jié)束時，如果low != n-1，Alow >=

59、0，如果low>0，Alow-1 < 0 */if(low > 0 && abs(Alow-1) < abs(Alow)return low-1;elsereturn low;8，問題：給定一個有序（非降序）數(shù)組A和一個有序（非降序）數(shù)組B，可含有重復(fù)元素，求兩個數(shù)組合并結(jié)果中的第k(k>=0)個數(shù)字。這個題目出現(xiàn)了兩個數(shù)組，有序的，不管怎樣我們就應(yīng)該首先考慮二分查找是否可行。若使用順序查找，時間復(fù)雜度最低為O(k)，就是類似歸并排序中的歸并過程。使用用二分查找時間復(fù)雜度為O(logM+logN)。二分查找的具體實現(xiàn)過程請參考實現(xiàn)代碼與注釋。cpp

60、 view plain copyprint?1. int findKthIn2SortedArrays(int A, int m, int B, int n, int k)  2.   3.     if(m <= 0) / 數(shù)組A中沒有元素，直接在B中找第k個元素  4.       

61、60; return Bk;  5.     if(n <= 0) / 數(shù)組B中沒有元素，直接在A中找第k個元素  6.         return Ak;  7.     int i = (m-1)>>1; / 數(shù)組A的中間位置 

62、; 8.     int j = (n-1)>>1; / 數(shù)組B的中間位置  9.     if(Ai <= Bj)  / 數(shù)組A的中間元素小于等于數(shù)組B的中間元素  10.       11.         

63、/* 12.         設(shè)x為數(shù)組A和數(shù)組B中小于Bj的元素數(shù)目，則i+1+j+1小于等于x， 13.         因為Ai+1到Am-1中還可能存在小于等于Bj的元素； 14.         如果k小于i+1+j+1，那么要查找的第k個元素肯定小于等于Bj， 15.    &

64、#160;    因為x大于等于i+1+j+1；既然第k個元素小于等于Bj，那么只 16.         需要在A0Am-1和B0Bj中查找第k個元素即可，遞歸調(diào)用下去。 17.         */  18.         if(k < i+1+j

65、+1)  19.           20.             if(j > 0)  21.                 return 

66、;findKthIn2SortedArrays(A, m, B, j+1, k);  22.             else / j = 0時特殊處理，防止死循環(huán)  23.               24. 

67、0;               if(k = 0)  25.                     return min(A0, B0);  26.  &#

68、160;              if(k = m)  27.                     return max(Am-1, B0);  28.  

69、0;              return Ak < B0 ? Ak : max(Ak-1, B0);  29.               30.      &

70、#160;    31.         /* 32.         設(shè)y為數(shù)組A和數(shù)組B中小于于等于Ai的元素數(shù)目，則i+1+j+1大于等于y； 33.         如果k大于等于i+1+j+1，那么要查找到第k個元素肯定大于Ai，因為 34.    

71、     i+1+j+1大于等于y；既然第k個元素大于Ai，那么只需要在Ai+1Am-1 35.         和B0Bn-1中查找第k-i-1個元素，遞歸調(diào)用下去。 36.         */  37.         else  38. &#

72、160;           return findKthIn2SortedArrays(A+i+1, m-i-1, B, n, k-i-1);  39.        40.     / 如果數(shù)組A的中間元素大于數(shù)組B的中間元素，那么交換數(shù)組A和B，重新調(diào)用即可  41. &#

73、160;   else  42.         return findKthIn2SortedArrays(B, n, A, m, k);  43.   int findKthIn2SortedArrays(int A, int m, int B, int n, int k)if(m <= 0) / 數(shù)組A中沒有元素，直接在B中找第k個元素return Bk;if(n

74、<= 0) / 數(shù)組B中沒有元素，直接在A中找第k個元素return Ak;int i = (m-1)>>1; / 數(shù)組A的中間位置int j = (n-1)>>1; / 數(shù)組B的中間位置if(Ai <= Bj) / 數(shù)組A的中間元素小于等于數(shù)組B的中間元素/*設(shè)x為數(shù)組A和數(shù)組B中小于Bj的元素數(shù)目，則i+1+j+1小于等于x，因為Ai+1到Am-1中還可能存在小于等于Bj的元素；如果k小于i+1+j+1，那么要查找的第k個元素肯定小于等于Bj，因為x大于等于i+1+j+1；既然第k個元素小于等于Bj，那么只需要在A0Am-1和B0Bj中查找第k個元素即可

75、，遞歸調(diào)用下去。*/if(k < i+1+j+1)if(j > 0)return findKthIn2SortedArrays(A, m, B, j+1, k);else / j = 0時特殊處理，防止死循環(huán)if(k = 0)return min(A0, B0);if(k = m)return max(Am-1, B0);return Ak < B0 ? Ak : max(Ak-1, B0);/*設(shè)y為數(shù)組A和數(shù)組B中小于于等于Ai的元素數(shù)目，則i+1+j+1大于等于y；如果k大于等于i+1+j+1，那么要查找到第k個元素肯定大于Ai，因為i+1+j+1大于等于y；既然第k個

76、元素大于Ai，那么只需要在Ai+1Am-1和B0Bn-1中查找第k-i-1個元素，遞歸調(diào)用下去。*/elsereturn findKthIn2SortedArrays(A+i+1, m-i-1, B, n, k-i-1); / 如果數(shù)組A的中間元素大于數(shù)組B的中間元素，那么交換數(shù)組A和B，重新調(diào)用即可elsereturn findKthIn2SortedArrays(B, n, A, m, k);9問題：一個有序（升序）數(shù)組，沒有重復(fù)元素，在某一個位置發(fā)生了旋轉(zhuǎn)后，求target在變化后的數(shù)組中出現(xiàn)的位置，不存在則返回-1如 0 1 2 4 5 6 7 可能變成 4 5 6 7 0 1 2我們

77、先比較中間元素是否是目標(biāo)值，如果是返回位置。如果不是，我們就應(yīng)該想辦法將搜索區(qū)間減少一半。因為存在旋轉(zhuǎn)變化，所以我們要多做一些判斷。我們知道因為只有一次旋轉(zhuǎn)變化，所以中間元素兩邊的子數(shù)組肯定有一個是有序的，那么我們可以判斷target是不是在這個有序的子數(shù)組中，從而決定是搜索這個子數(shù)組還是搜索另一個子數(shù)組。具體請參考實現(xiàn)代碼與注釋。cpp view plain copyprint?1. int searchInRotatedArray(int A, int n, int target)   2. 

78、0; 3.     int low = 0, high = n-1;  4.     while(low <= high)  5.       6.         int mid = low+(high-low)

79、>>1);  7.         if(Amid = target)   8.             return mid;  9.         if(Amid >= Alo

80、w)   10.           11.             / low  mid 是升序的  12.             if(target &g

81、t;= Alow && target < Amid)  13.                 high = mid-1;  14.             else  

82、;15.                 low = mid+1;  16.           17.         else  18.      

83、;     19.             / mid  high 是升序的  20.             if(target > Amid && target <=&

84、#160;Ahigh)  21.                 low = mid+1;  22.             else  23.         

85、;        high = mid-1;  24.           25.       26.     return -1;  27.   int searchInRotatedArray(int A, int n, in

86、t target) int low = 0, high = n-1;while(low <= high)int mid = low+(high-low)>>1);if(Amid = target) return mid;if(Amid >= Alow) / low mid 是升序的if(target >= Alow && target < Amid)high = mid-1;elselow = mid+1;else/ mid high 是升序的if(target > Amid && target <= Ahigh)

87、low = mid+1;elsehigh = mid-1;return -1;如果這樣的數(shù)組中存在重復(fù)元素，還能使用二分嗎？答案是不能。請看幾個例子1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1這些都是有第一個數(shù)組旋轉(zhuǎn)一次變化來的，我們不能通過二分確定是否存在元素1.10，問題：一個有序（升序）數(shù)組，沒有重復(fù)元素，在某一個位置發(fā)生了旋轉(zhuǎn)后，求最小值所在位置如果中間元素小于左端元素，則最小值在左半?yún)^(qū)間內(nèi)（包含中間元素）；如果中間元素大于右端元素，則最小值在右半?yún)^(qū)間內(nèi)（包含中間元素）。請參考實現(xiàn)代碼

88、與注釋。cpp view plain copyprint?1. int searchMinInRotatedArray(int A, int n)   2.   3.     if(n = 1)  4.         return 0;  5.     int low

89、 = 0, high = n-1;  6.     while(low < high-1) / 保證mid != low且mid != high  7.       8.         int mid = low

90、+(high-low)>>1);  9.         if(Amid < Alow) / 最小值在lowmid  10.             high = mid;  11.       

91、60; else / Amid > Alow, / 最小值在mid和high之間  12.             low = mid;  13.       14.     return Alow < Al

92、ow+1 ? low : low+1;  15.   int searchMinInRotatedArray(int A, int n) if(n = 1)return 0;int low = 0, high = n-1;while(low < high-1) / 保證mid != low且mid != highint mid = low+(high-low)>>1);if(Amid < Alow) / 最小值在lowmidhigh = mid;else / Amid > Alow,

93、/ 最小值在mid和high之間low = mid;return Alow < Alow+1 ? low : low+1;11,問題：一個有序（升序）數(shù)組，沒有重復(fù)元素，在某一個位置發(fā)生了旋轉(zhuǎn)后，求第k(k > 0)小元素的位置我們可以利用上一題的解答，求出最小值所在位置后，便可以求出第k小元素。請參考實現(xiàn)代碼與注釋cpp view plain copyprint?1. int searchKthInRotatedArray(int A, int n, int k)   2.  &#

94、160;3.     int posMin = searchMinInRotatedArray(A, n);  4.     return (posMin+k-1)%n;  5.   int searchKthInRotatedArray(int A, int n, int k) int posMin = searchMinInRotatedArray(A, n);return (posMin+k-1)%n

95、;12，查找旋轉(zhuǎn)數(shù)組的最小數(shù)字題目：即找分界點，比如3 4 5 1 2，返回的是位置3。以題目中的旋轉(zhuǎn)數(shù)組為例，3,4,5,1,2，我們可以有序數(shù)組經(jīng)過旋轉(zhuǎn)以后被分割為兩段有序的數(shù)組，比如此處被分為3,4,51,2這樣連個數(shù)組，并且前半段數(shù)組中的數(shù)字肯定大于等于后半段的數(shù)組。我們找中間元素amid，讓其跟元素首元素alow和尾元素ahigh比較，如果大于首元素alow，則中間元素屬于前半段有序數(shù)組；如果小于尾元素ahigh，那么中間元素就是后半段的元素。這里我們設(shè)定兩個指針start和end分別指向數(shù)組的首尾元素，然后當(dāng)start指向前半段最后一個元素，end指向后半段第一個元素，這是程序就找

96、到了數(shù)組中的最小元素，就是end指向的那個數(shù)，程序的出口就是 end-start=1。cpp view plain copyprint?1. int bSearchMinValue(int a, int low, int high)  2.     /終止遞歸條件是low和high差1，原因是后面mid都不是+1-1處理的  3.     if(low+1=high)  4.