二分查找問題全集OK

http://blog.csdn.net/luckyxiaoqiang/article/details/8937978

1，原始二分查找

題目：給定一個有序（非降序）數組A，求任意一個i使得A[i]等于target，不存在則傳回-1

例如：[2,4,6,8,9]找(4) 位置1

1.1 遞歸版

int bSearch(int a[], int low, int high, int target){
	if(low > high)
		return -1;
	int mid = (low + high)/2;
	if(target<a[mid])
		return bSearch(a,low,mid-1,target);
	else if(target>a[mid])
		return bSearch(a,mid+1,high,target);
	//if(target == a[mid])
	return mid;
}

1.2 疊代版

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(A[mid] == target)
			return mid;
		else if(A[mid] < target)
			low = mid+1;
		else // A[mid] > target
			high = mid-1;
	}
	return -1;
}

1.3 傳回插入位置

給定一個有序（非降序）數組A，若target在數組中出現，傳回位置，若不存在，傳回它應該插入的位置。

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(A[mid] == target)
			return mid;
		else if(A[mid] < target)
			low = mid+1;
		else // A[mid] > target
			high = mid-1;
	}
	return -(low+1);
}

之是以傳回-（low+1）而不是直接傳回-low是因為low可能為0，如果直接傳回-low就無法判斷是正常傳回位置0還是查找不成功傳回的0。

2，含重複元素，求=target的最小一個

問題：給定一個有序（非降序）數組A，可含有重複元素，求最小的i使得A[i]等于target，不存在則傳回-1

例如：A[2,4,6,8,8,8,9]求8得最小位置3

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(A[mid] == target)
		{
			if(mid > 0 && A[mid-1] == target)
				high = mid-1;           
			else 
				return mid;
		}
		else if(A[mid] < target)
			low = mid+1;             
		else // A[mid] > target
			high = mid-1;           
	}
    return -(low+1);  
}

3，含重複元素，求=target的最大一個

問題：給定一個有序（非降序）數組A，可含有重複元素，求最大的i使得A[i]等于target，不存在則傳回-1

例如：A[2,4,6,8,8,8,9]求8得最大位置5

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(A[mid] == target)
		{
			if(mid < n-1 && A[mid+1] == target)
				low = mid+1;           
			else 
				return mid;
		}
		else if(A[mid] < target)
			low = mid+1;             
		else // A[mid] > target
			high = mid-1;           
	}
    return -(low+1);  
}

4，含重複元素，求<target的最大一個

問題：給定一個有序（非降序）數組A，可含有重複元素，求最大的i使得A[i]小于target，不存在則傳回-1

例如：A[2,4,6,8,8,8,9]求9得最大位置5 問題轉化：含重複元素，求2【=target的最小一個】的前一個。

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(A[mid] == target)
		{
			if(mid > 0 && A[mid-1] == target)
				high = mid-1;           
			else 
				return (mid==0)?-1:mid-1;
		}
		else if(A[mid] < target)
			low = mid+1;             
		else // A[mid] > target
			high = mid-1;           
	}
    return -(low+1);  
}

5，含重複元素，求>target的最小一個

問題：給定一個有序（非降序）數組A，可含有重複元素，求最小的i使得A[i]大于target，不存在則傳回-1 例如：A[2,4,6,8,8,8,9]求6的最小位置3

問題轉化：含重複元素，求3【=target的最大一個】的後一個。

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(A[mid] == target)
		{
			if(mid < n-1 && A[mid+1] == target)
				low = mid+1;           
			else 
				return (mid==n-1)?-n:mid+1;
		}
		else if(A[mid] < target)
			low = mid+1;             
		else // A[mid] > target
			high = mid-1;           
	}
    return -(low+1);  
}

6，含重複元素，求=target的出現次數

問題：給定一個有序（非降序）數組A，可含有重複元素，求target在數組中出現的次數。例如：A[2,4,6,8,8,8,9]求8的出現次數3

求出第一次出現位置和最後一次出現位置。由于前面都已實作，這裡不多解釋。請參考實作代碼與注釋

int count(int A[], int n, int target)
{
	int firstPos = searchFirstPos(A, n, target); // 第一次出現位置
	if(firstPos == -1)
		return 0;
	int lastPos = searchLastPos(A, n, target);  // 最後一次出現位置
	return lastPos-firstPos+1;  // 出現次數
}

7，含重複元素，求絕對值最小的元素

問題：給定一個有序（非降序）數組A，可含有重複元素，求絕對值最小的元素的位置

例如：A[-4,-2,-1,2,3,8,9]求結果為2

int searchMinAbs(int A[], int n)
{
	int low = 0, high = n-1;
	while(low < high)
	{
		int mid = low+((high-low)>>1);
		if(A[mid] < 0)
			low = mid+1;
		else // A[mid] >= 0
			high = mid;
	}
	/* 循環結束時，如果low != n-1，A[low] >= 0，如果low>0，A[low-1] < 0 */
	if(low > 0 && abs(A[low-1]) < abs(A[low]))
		return low-1;
	else
		return low;
}

8，問題：給定一個有序（非降序）數組A和一個有序（非降序）數組B，可含有重複元素，求兩個數組合并結果中的第k(k>=0)個數字。

這個題目出現了兩個數組，有序的，不管怎樣我們就應該首先考慮二分查找是否可行。若使用順序查找，時間複雜度最低為O(k)，就是類似歸并排序中的歸并過程。使用用二分查找時間複雜度為O(logM+logN)。二分查找的具體實作過程請參考實作代碼與注釋。

int findKthIn2SortedArrays(int A[], int m, int B[], int n, int k)
{
	if(m <= 0) // 數組A中沒有元素，直接在B中找第k個元素
		return B[k];
	if(n <= 0) // 數組B中沒有元素，直接在A中找第k個元素
		return A[k];
	int i = (m-1)>>1; // 數組A的中間位置
	int j = (n-1)>>1; // 數組B的中間位置
	if(A[i] <= B[j])  // 數組A的中間元素小于等于數組B的中間元素
	{
		/*
		設x為數組A和數組B中小于B[j]的元素數目，則i+1+j+1小于等于x，
		因為A[i+1]到A[m-1]中還可能存在小于等于B[j]的元素；
		如果k小于i+1+j+1，那麼要查找的第k個元素肯定小于等于B[j]，
		因為x大于等于i+1+j+1；既然第k個元素小于等于B[j]，那麼隻
		需要在A[0]~A[m-1]和B[0]~B[j]中查找第k個元素即可，遞歸調用下去。
		*/
		if(k < i+1+j+1)
		{
			if(j > 0)
				return findKthIn2SortedArrays(A, m, B, j+1, k);
			else // j == 0時特殊處理，防止死循環
			{
				if(k == 0)
					return min(A[0], B[0]);
				if(k == m)
					return max(A[m-1], B[0]);
				return A[k] < B[0] ? A[k] : max(A[k-1], B[0]);
			}
		}
		/*
		設y為數組A和數組B中小于于等于A[i]的元素數目，則i+1+j+1大于等于y；
		如果k大于等于i+1+j+1，那麼要查找到第k個元素肯定大于A[i]，因為
		i+1+j+1大于等于y；既然第k個元素大于A[i]，那麼隻需要在A[i+1]~A[m-1]
		和B[0]~B[n-1]中查找第k-i-1個元素，遞歸調用下去。
		*/
		else
			return findKthIn2SortedArrays(A+i+1, m-i-1, B, n, k-i-1);
	} 
	// 如果數組A的中間元素大于數組B的中間元素，那麼交換數組A和B，重新調用即可
	else
		return findKthIn2SortedArrays(B, n, A, m, k);
}

9 問題：

一個有序（升序）數組，沒有重複元素，在某一個位置發生了旋轉後，求target在變化後的數組中出現的位置，不存在則傳回-1 如 0 1 2 4 5 6 7 可能變成 4 5 6 7 0 1 2

我們先比較中間元素是否是目标值，如果是傳回位置。如果不是，我們就應該想辦法将搜尋區間減少一半。因為存在旋轉變化，是以我們要多做一些判斷。我們知道因為隻有一次旋轉變化，是以中間元素兩邊的子數組肯定有一個是有序的，那麼我們可以判斷target是不是在這個有序的子數組中，進而決定是搜尋這個子數組還是搜尋另一個子數組。具體請參考實作代碼與注釋。

int searchInRotatedArray(int A[], int n, int target) 
{
	int low = 0, high = n-1;
	while(low <= high)
	{
		int mid = low+((high-low)>>1);
		if(A[mid] == target) 
			return mid;
		if(A[mid] >= A[low]) 
		{
			// low ~ mid 是升序的
			if(target >= A[low] && target < A[mid])
				high = mid-1;
			else
				low = mid+1;
		}
		else
		{
			// mid ~ high 是升序的
			if(target > A[mid] && target <= A[high])
				low = mid+1;
			else
				high = mid-1;
		}
	}
	return -1;
}

如果這樣的數組中存在重複元素，還能使用二分嗎？答案是不能。請看幾個例子

[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]這些都是有第一個數組旋轉一次變化來的，我們不能通過二分确定是否存在元素1.

10，問題：一個有序（升序）數組，沒有重複元素，在某一個位置發生了旋轉後，求最小值所在位置如果中間元素小于左端元素，則最小值在左半區間内（包含中間元素）；如果中間元素大于右端元素，則最小值在右半區間内（包含中間元素）。請參考實作代碼與注釋。

int searchMinInRotatedArray(int A[], int n) 
{
	if(n == 1)
		return 0;
	int low = 0, high = n-1;
	while(low < high-1) // 保證mid != low且mid != high
	{
		int mid = low+((high-low)>>1);
		if(A[mid] < A[low]) // 最小值在low~mid
			high = mid;
		else // A[mid] > A[low], // 最小值在mid和high之間
			low = mid;
	}
	return A[low] < A[low+1] ? low : low+1;
}

11, 問題：

一個有序（升序）數組，沒有重複元素，在某一個位置發生了旋轉後，求第k(k > 0)小元素的位置

我們可以利用上一題的解答，求出最小值所在位置後，便可以求出第k小元素。請參考實作代碼與注釋

int searchKthInRotatedArray(int A[], int n, int k) 
{
	int posMin = searchMinInRotatedArray(A, n);
	return (posMin+k-1)%n;
}

12，查找旋轉數組的最小數字

題目：即找分界點，比如3 4 5 1 2，傳回的是位置3。以題目中的旋轉數組為例，{3,4,5,1,2}，我們可以有序數組經過旋轉以後被分割為兩段有序的數組，比如此處被分為{3,4,5}{1,2}這樣連個數組，并且前半段數組中的數字肯定大于等于後半段的數組。我們找中間元素a[mid]，讓其跟元素首元素a[low]和尾元素a[high]比較，如果大于首元素a[low]，則中間元素屬于前半段有序數組；如果小于尾元素a[high]，那麼中間元素就是後半段的元素。這裡我們設定兩個指針start和end分别指向數組的首尾元素，然後當start指向前半段最後一個元素，end指向後半段第一個元素，這是程式就找到了數組中的最小元素，就是end指向的那個數，程式的出口就是 end-start==1。

int bSearchMinValue(int a[], int low, int high){
	//終止遞歸條件是low和high差1，原因是後面mid都不是+1-1處理的
	if(low+1==high)
		return high;
	int mid = (low + high)/2;

	if(a[mid]>a[low])//左側有序，在右邊找分界點
		return bSearchMinValue(a,mid,high);
	if(a[mid]<a[high])//右側有序，在左邊找分界點
		return bSearchMinValue(a,low,mid);
	return -1;
}

特别注意，如果數組a不是旋轉數組，則會錯誤。

13，查找旋轉數組的任意數字

http://hi.baidu.com/nicker2010/item/4d4f71145532a234b83180a7

例如：仔細分析該問題，可以發現，每次根據low和high求出mid後，mid左邊（[low, mid]）和右邊（[mid, high]）至少一個是有序的。

a[mid]分别與a[left]和a[right]比較，确定哪一段是有序的。

如果左邊是有序的，若target<a[mid]且target>a[left], 則right=mid-1；其他情況，left =mid+1；

如果右邊是有序的，若target> a[mid] 且target<a[right] 則left=mid+1；其他情況，right =mid-1；

//旋轉數組的二分查找
int bSearchMinValue(int a[], int low, int high, int target){
	
	int mid = (low + high)/2;
	
	//就是a[mid]
	if(target == a[mid])
		return mid;
		
	if(a[mid]>=a[low]){//左側有序，在右邊有分界點
		//在左側有序的之中
		if(target>=a[low]&&target<a[mid])
			return bSearchMinValue(a,low,mid-1,target);
		//在右側有分界點之中
		else
			return bSearchMinValue(a,mid+1,high,target);
	}
	else if(a[mid]<=a[high]){//右側有序，在左邊有分界點
		//在右側有序的之中
		if(target>a[mid]&&target<=a[high])
			return bSearchMinValue(a,mid+1,high,target);
		//在左側有分界點之中
		else
			return bSearchMinValue(a,low,mid-1,target);
	}
	return -1;
}

二分查找問題全集OK

1，原始二分查找

1.1 遞歸版

1.2 疊代版

1.3 傳回插入位置

2，含重複元素，求=target的最小一個

3，含重複元素，求=target的最大一個

4，含重複元素，求<target的最大一個

5，含重複元素，求>target的最小一個

6，含重複元素，求=target的出現次數

7，含重複元素，求絕對值最小的元素

12，查找旋轉數組的最小數字

13，查找旋轉數組的任意數字

繼續閱讀

斐波那契數列的兩種解題思路：遞歸VS疊代

Understanding Steering Behaviors: Seek (行為控制-尋找)原文位址連結：http://gamedevelopment.tutsplus.com/tutorials/understanding-steering-behaviors-seek--gamedev-849位置，速度和移動計算力增加力結論

【leetcode】188. Best Time to Buy and Sell Stock IV

減繩子問題動态規劃求解

算法設計9-最小正整數問題算法設計9-最小正整數問題

POJ1013稱硬币枚舉法

為什麼普通人難以掌握資訊學奧林匹克競賽的知識？·由于資訊學奧賽涉及抽象的概念和算法，需要運用數學思維和邏輯推理能力來解決

判斷某日是該年第幾天

整數變換問題(C語言)--回溯法

Arab Collegiate Programming Contest 2012G. Archery(求雷達掃描的期望，區間離散化)

算法設計學習：單連結清單算法

9個offer，12家公司，35場面試，從微軟到谷歌，應屆計算機畢業生的2012求職之路[對書籍加了注釋]

短視訊美顔SDK的抖動功能是怎麼實作的

【原創】TOP k算法的簡單實作

JSON性能比對 Json BecnhMark

算法基礎遍之選擇排序算法詳解