合縱連橫: 二分搜尋法框架_理解背後的本質

Ian Taylor on Unsplash

這篇文章，會帶著大家複習以前學過的二分搜尋法(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 二分搜索法的框架，還有相關的衍伸變化題與演算法建造流程，

希望能幫助讀者、觀眾徹底理解它的原理，

並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！

感謝收看囉! 我們下篇文章再見~