Leetcode刷題筆記——二分法

二分法是搜尋演演算法中極其典型的方法，其要求輸入序列有序並可隨機存取。演演算法思想為

輸入：有序陣列nums，目的數值target
要求輸出：如果target存在在陣列中，則輸出其index，否則輸出-1

1. 將原陣列通過[left,right]兩個索引劃分範圍，初值left=0,right=陣列的最後一個元素
2. 當left <= right時
   1. middle = (left + right)/2
   2. 判斷nums[middle]是不是要查詢的target，如果是則返回結果
   3. 判斷nums[middle]> target，證明要查詢的target在左邊，因此right = middle - 1
   4. 判斷nums[middle]< target，證明要查詢的target在右邊，因此left = middle + 1
3. 沒有查詢到return -1。

形如下圖：

傳統的二分法程式碼如下：

func binarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		middle := (left + right) / 2
		if nums[middle] == target {
			return middle
		} else if nums[middle] > target {
			right = middle - 1
		} else {
			left = middle + 1
		}
	}
	return -1
}

這裡要注意兩個問題：

1. 上述演演算法中的第2步中=的判斷，即for left <= right還是for left < right。
2. 上述演演算法2.2-2.4中的判斷條件以及下一次查詢區間的設定
3. 返回值代表什麼意思

for left<= right 中 = 的判斷

首先對於第一個問題，=是否應該存在，取決於對於二分查詢的初始化定義，例如：

1. 如果二分查詢遍歷的區間採用[left,right]（數學中的雙閉區間）的形式，考慮left==right即=成立的情況，則表示區間內只有單個運算元，這種情況還是需要處理，否則無法通過其餘方式表示這種情況，所以此時=是必須的。
2. 如果二分查詢遍歷的區間採用[left,right)的形式，考慮left==right即=成立的情況，事實證明，這種情況並不應該存在，我們無法用[i,i)表示任何一個區間，所以，這種情況下，=就不是必須的。

判斷條件以及下一次查詢區間的設定

然後考察對於第二個問題，判斷條件以及下一次查詢區間應該如何設定？

注意：二分查詢是一個經典的查詢演演算法，其目的是查詢到指定的位置或者值，並不僅限於查詢到等於target的index這一種情況。

但無論怎樣，二分查詢本身有一個固定模式，即二分，就是從middle處將區間[left,right]分成兩份，然後根據middle的情況查詢（或者更新新的區間），因此，我們只需要考慮清楚如下三種條件時要怎麼處理即可：

1. 當遍歷到nums[middle] == target時應該怎樣處理（新的查詢區間是什麼），即當前值等於目標值
2. 當遍歷到nums[middle] > target時應該怎樣處理（新的查詢區間是什麼），即當前值大於目標值
3. 當遍歷到nums[middle] < target時應該怎樣處理（新的查詢區間是什麼），即當前值小於目標值

討論完上述兩個問題，其實二分法就有了一個固定的框架：

func binarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		middle := (left + right) / 2
		if nums[middle] == target {
			// 當前值等於目標值時，如何處理（新的查詢區間是什麼）
		} else if nums[middle] > target {
			// 當前值大於目標值時，如何處理（新的查詢區間是什麼）
		} else {
			// 當前值小於目標值時，如何處理（新的查詢區間是什麼）
		}
	}
    // 考慮返回值的意義
	return 
}

返回值的含義

最後我們討論返回值的含義這一話題。在傳統的二分查詢中，只有在兩種情況下會返回：

1. 查詢到目標target，返回查詢到的index
2. 未查詢到目標target，返回-1。（即文章最起始處 步驟3的含義）

這裡返回值的含義表示target在nums中的index，該值只會出現在nums[middle]==target這一條件下。然而，剛才提到了二分查詢不總是處理等式條件，因此我們總要思考兩種返回值的含義：

1. nums[middle]==target，這時return代表的是什麼？
2. 陣列中不存在target，此時return的是什麼，此時left、right代表什麼？

這裡我們舉一個稍稍複雜一點的例子對二分查詢進行分析。

• 搜尋插入位置
• 在排序陣列中查詢元素的第一個和最後一個位置

搜尋插入位置

題目要求如下：

這個問題要求返回兩種返回值：

1. 在陣列中找到目標值，並返回其索引
2. 如果目標值不存在於陣列中，返回它將會被按順序插入的位置

其中對於情況1，傳統的二分查詢演演算法就可以解決，而情況2，則需要藉助於本部分要講解的返回值的含義。

對於傳統的二分法：

func binarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		middle := (left + right) / 2
		if nums[middle] == target {
			return middle
		} else if nums[middle] > target {
			right = middle - 1
		} else {
			left = middle + 1
		}
	}
	return -1
}

如果target能在nums陣列中查詢到，必定最終查詢到一個[i,i]型別的區間，即區間中只有一個數位，否則區間就要再次進行二分。例如：如果要在下列陣列中查詢4所在的位置，查詢過程如下，第三步時，查詢區間為[2,3]，有兩個值，無法確定答案，則需要再次進行一次查詢：

target == 4
nums   1  2  3  4
index  0  1  2  3
1      l        r
2         l     r
3            l  r
4               lr 

那麼最終我們處理的情況必定是對於區間[left,right]中，其中left == right，因此middle == left == right，此時nums[middle]和target的關係。

• nums[middle] > target，則需要從middle左側繼續尋找，right = middle - 1，注意此時left = middle，left > right
• nums[middle] < target，則需要從middle右側繼續尋找，left = middle + 1，注意此時right = middle，left > right

所以此時，left指向的永遠是大的那個值，right是小的那個值（因為left <= right時，迴圈不會終止，迴圈終止條件為left > right，根據陣列的有序性，nums[left] > nums[right]）。

最後，我們考察該題，對於陣列nums，如果目標值不在其中，那麼其最終查詢到的值只有兩種情況：

1. nums[middle] < target，此時nums[middle]應該是第一個小於target的值，如果要查詢target所在位置，應該返回大於middle的index，即left
2. nums[middle] > target，此時nums[middle]應該是第一個大於target的值，如果要查詢target所在位置，應該返回等於middle的index，用target替換middle位置的值，即left

因此，該題的結果，只需要修改傳統二分查詢的最後一行：

func binarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		middle := (left + right) / 2
		if nums[middle] == target {
			return middle
		} else if nums[middle] > target {
			right = middle - 1
		} else {
			left = middle + 1
		}
	}
	return left 
}

在排序陣列中查詢元素的第一個和最後一個位置

題目要求如下：

注意這裡查詢的是元素第一次和最後一次出現的位置，這裡我們以查詢第一次出現的位置舉例，後者同理。

考察我們在判斷條件以及下一次查詢區間的設定中強調的，考察二分查詢的三種情況：

情況	分析	操作
nums[middle] == target時，即當前值等於目標值	第一次出現的位置可能在當前值前面	right = middle - 1
nums[middle] > target時，即當前值大於目標值	第一次出現的位置在當前值前面	right = middle - 1
nums[middle] < target時，即當前值小於目標值	第一次出現的位置在當前值後面	left = middle + 1

與之前不同的是當nums[middle] == target時，不再有返回值了，那麼考慮最後返回值的含義，最終left > right時情況有如下3種：

情況	分析	操作
nums[middle] == target	此時，middle前的值必定<middle，而不是等於（只要等於，考慮上表的情況1，會使right = middle - 1）	return left
nums[middle] > target	此情況不存在，因為如果有這種情況會繼續使right=middle-1	不進行操作
nums[middle] < target	此時middle必定是target前的第一個元素	return left

經過上面的分析後，可以清晰的寫出程式碼：

    l, r := 0, len(nums)-1
	for l <= r {
		m := (l + r) / 2
		if nums[m] >= target {
			r = m - 1
		} else {
			l = m + 1
		}
	}
    result := l

而查詢元素出現的最後一個位置，只需要反過來，最後return right即可。程式碼如下：

    l, r: = 0, len(nums)-1
	for l <= r {
		m := (l + r) / 2
		if nums[m] <= target {
			l = m + 1
		} else {
			r = m - 1
		}
	}
    result := r

總結

本文詳細分析了二分查詢的所有細節，對於二分查詢處理的問題，我們常常需要更加關注本文討論的後兩個問題：

1. 判斷條件以及下一次查詢區間的設定
2. 返回值的含義

最後填充模版即可。

func binarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		middle := (left + right) / 2
		if nums[middle] == target {
			// 當前值等於目標值時，如何處理（新的查詢區間是什麼）
		} else if nums[middle] > target {
			// 當前值大於目標值時，如何處理（新的查詢區間是什麼）
		} else {
			// 當前值小於目標值時，如何處理（新的查詢區間是什麼）
		}
	}
    // 考慮返回值的意義
	return 
}