合縱連橫: 二分搜尋法框架_理解背後的本質
這篇文章，會帶著大家複習以前學過的二分搜尋法(Binary Search)框架，
並且以二分搜尋法的概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個實用的演算法框架。
Binary search 二分搜尋法框架
用途:
在已經排序好的數列中尋找目標值。
在單調遞增、或單調遞減的f(x)尋找滿足某個條件的目標值。
在具有局部最大值，或局部最小值的f(x)中尋找最大值(高峰)、最小值(低谷)。
def search(arr, target):
left, right = 0, len(right):
while left <= right:
# 使用比較安全的計算方式，避免整數溢位 avoid integer overflow
# 使用C/C++, Java...等語言的讀者請留意
mid = left + (right - left ) // 2
# 假如找到目標值，或者滿足某個特定條件，代表成功
if arr[mid] == target:
return mid
elif arr[mid] > target:
# 目前的值還太大，下一輪只搜尋左半部。
right = mid - 1
else:
# 目前的值還太小，下一輪只搜尋右半部
left = mid + 1
return -1
接下來，我們會用這個上面這種結構，貫穿一些同類型，有關聯的題目
(請讀者、或觀眾留意上面的這種 二分搜尋 框架，之後的解說會反覆出現)
剛好以前有錄過其中一題範例Guess Number的教學影片，提供給讀者參考。
Binary search 二分搜尋法 (最普通的應用，也是常見的課本範例)
在一個已經排序好的陣列nums中，尋找目標值target
用二分搜尋 框架來解，就變成下面這個樣子
Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0,len(nums)-1
while left <= right:
if not (nums[left] <= target <= nums[right]):
# optimization, early stop unnecessary branch
return-1
mid = left + ( right - left ) // 2
if( nums[mid] == target):
return mid
elif nums[mid] < target:
left = mid+1
else:
right = mid-1
return -1
好，接下來，來看一道相關的變化題
在平移過，已排序的陣列搜尋目標值
假如這個陣列是排序好的，但是被平移過，還可以使用二分搜尋嗎?
其實可以喔，只要多加一個判斷:
目前是左邊已排序而且趨勢連續，還是右邊已排序而且趨勢連續?
假如左邊已排序而且趨勢連續，看看target有沒有落在左邊的範圍，如果有，下次就搜尋左半部；如果沒有，下次就搜尋右半部。
同樣的，另一邊也是對稱的形式。
假如右邊已排序而且趨勢連續，看看target有沒有落在右邊的範圍，如果有，下次就搜尋右半部；如果沒有，下次就搜尋左半部。
示意圖
image
用二分搜尋 框架來解，就變成下面這個樣子
class Solution:
def search(self, nums: List[int], target: int) -> int:
def helper_binary_search( nums, start, end, target):
while start <= end:
mid = start + (end-start)//2
if nums[mid] == target:
# base case:
# hit
return mid
# Divide-and-conquer
if nums[mid] < nums[end]:
# right half keeps sorted in ascending order after rotation
if nums[end] >= target > nums[mid]:
if not (nums[mid] <= target <= nums[end]):
return -1
# search target in right half
start = mid+1
else:
# search target in left half
end = mid-1
else:
# left half keeps sorted in ascending order after rotation
if nums[start] <= target < nums[mid]:
if not (nums[start] <= target <= nums[mid]):
return -1
# search target in left half
end = mid-1
else:
# search target in right half
start = mid+1
# base case:
# miss
# target does not exist in the list
return -1
# ============================================
return helper_binary_search(nums, 0, len(nums)-1, target)
接下來再看一道常見的變形題
找目標值第一次出現和最後一次出現的位置。
在已排序的陣列中，找目標值的第一次出現和最後一次出現的索引位置。
怎麼做呢? 其實很直覺！
找第一次出現的索引，就是一直往左邊找目標值，直到找不到為止。
另一邊，也是對稱的
找最後一次出現的索引，就是一直往右邊找目標值，直到找不到為止。
用二分搜尋 框架來解，就變成下面這個樣子
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# ------------------------------------
def find_first():
left, right = 0, len(nums)-1
index = -1
while left <= right:
mid = left + (right - left)//2
if nums[mid] == target:
index = mid
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return index
# ------------------------------------
def find_last():
left, right = 0, len(nums)-1
index = -1
while left <= right:
mid = left + (right - left)//2
if nums[mid] == target:
index = mid
left = mid + 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return index
# ------------------------------------
first_idx, last_idx = find_first(), find_last()
return [first_idx, last_idx]
順便介紹，如果用Python 原生內建的bisect二分模組也可以。
示意圖
image
使用Python原生內建的bisect模組:
from bisect import bisect_left, bisect_right
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# first index is the insertion index on the left
first = bisect_left( nums, target )
# last index is the insertion index on the right - 1
last = bisect_right( nums, target )-1
if first > last:
# target does not exist in nums
return [-1, -1]
else:
# target exist, report indices
return [ first, last ]
除了傳統的尋找目標值以外，還可以解一些具有已排序性質函數的題目喔！
例如 開根號這題。
計算某個整數x的平方根的整數部分
題目開門見山，要求我們計算某個整數x的平方根的整數部分，
而且不允許使用內建的sqrt()或者次方計算符號。
那麼除了暴力搜索、數值近似的牛頓法，還有沒有別的方法?
其實開根號這題也可以用 二分搜尋法 來解喔！
為什麼?
因為y = 根號 x = x ^ (0.5) 本身就是一個嚴格遞增的函數(相當於已排序)，如下圖
因此，搜索的初始化區間就變成了[0, x]，
目標值就用二分搜尋法來找，每次取中央點mid來測試，是否為x的平方根的整數部分。
假如mid * mid <= x，
那表示還可以往上搜索，看看能不能離真正的平方根更靠近一點。
假如mid*mid > x，
則表示mid太大，下一回合只要往下搜索即可。
最後離開迴圈時，right會剛好停在x的平方根的整數部分。
用二分搜尋 框架來解，就變成下面這個樣子
class Solution:
def mySqrt(self, x: int) -> int:
left, right = 0, x
while left <= right:
mid = left + (right - left) // 2
square = mid * mid
if square <= x:
left = mid + 1
elif square > x :
right = mid -1
return right
結語
好，今天一口氣介紹了最精華的部分，
通用的Binary search 二分搜索法的框架，還有相關的衍伸變化題與演算法建造流程，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
