Hi 大家好，昨天將binary search的題目分成三個類型:

1. 應用在array上，但是對於要回傳的index有不一樣的條件
2. 應用在不同的資料結構上，例如：二維陣列、二元樹、多個一維陣列
3. 保留上述binary search程式碼的框架，但是對於if statement的判斷由題目所定義，而非只是判斷數字大小

今天就要從第一個類型開始介紹起，讓我們開始吧

第一型

Leetcode 34. Find First and Last Position of Element in Sorted Array

題目敘述：有一個遞增的array，給予某個整數當作要從這個array中找出的目標。題目要求要找出符合這個目標且最左邊的index和最右邊的index。找不到目標時回傳-1。

Example1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

分析：
以下是原本的binary search程式碼，

def binarySearch(arr, target):
    l, r = 0, len(arr) - 1

    while l <= r:
        mid = (l + r) // 2

        if target > arr[mid]:
            l = mid + 1
        elif target < arr[mid]:
            r = mid - 1
        else:
            return mid
    return -1

對於第一型，根據條件來回傳不同的index的題目只要把握更改else裡的程式碼以及l = mid + 1，代表我們要將找尋的範圍往右移，所以會找到靠右邊的index；r = mid - 1，代表我們將找尋範圍往左移，所以會找到靠左邊的index。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        
        def binarySearch(target, leftBias):
            l, r = 0, len(nums) - 1
            res = -1

            while l <= r:
                m = (l + r) // 2

                if target > nums[m]:
                    l = m + 1
                elif target < nums[m]:
                    r  = m - 1
                else:
                    res = m
                    if leftBias:
                        r = m - 1
                    else:
                        l = m + 1
            
            return res
    
        ans = []
        ans.append(binarySearch(target, True))
        ans.append(binarySearch(target, False))
        return ans

因為要找出靠最左和最右邊的index，所以我們利用LeftBias來當作開關，leftBias為True代表要找出靠左的index。

追問：有一個target在array的最大值和最小值之間，找出在array中可以插入的最左邊的index和最右邊的index

def insert_in_left_or_right(nums, target, leftBias):
    l, r = 0, len(nums) - 1

    while l <= r:
        m = (l + r) // 2
        if target > nums[m]:
            l = m + 1
        elif target < nums[m]:
            r = m - 1
        else:
            if leftBias:
                r = m - 1
            else:
                l = m + 1
    
    return l if leftBias else r

# Example:
sorted_array = [1, 3, 3, 4, 4, 4, 5, 6]
target = 4
first_index = insert_in_left_or_right(sorted_array, target, True)
last_index = insert_in_left_or_right(sorted_array, target, False)
print(f"The target {target} should be inserted before index {first_index}")
print(f"The target {target} should be inserted after index {last_index}")

The target 4 should be inserted before index 3
The target 4 should be inserted after index 5

第二型

Leetcode 74. Search a 2D Matrix

題目敘述：給予一個 m x n的整數陣列，並且有以下特點：

• 每一列的數字都是遞增的
• 每一列的第一個數字會比上一列的最後一個數字大

需要一個O(log(m * n))的解答

Example:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

第二型會和平時的一維陣列不同的資料結構上使用binary search，像是本題是二維陣列。本題只需要將二維陣列拆解成m個一維陣列，並且在此執行binary search就可以得到答案。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def binarySearch(nums, target):
            l, r = 0, len(nums) - 1
            while l <= r:
                m = (l + r) // 2

                if target > nums[m]:
                    l = m + 1
                elif target < nums[m]:
                    r = m - 1
                else:
                    return True
            
            return False
        
        for nums in matrix:
            if nums[0] <= target <= nums[-1]:
                return binarySearch(nums, target)
        
        return False

第三型

Leetcode 875. Koko Eating Bananas

題目敘述：有隻猴子被給予了n堆的香蕉，美堆香蕉的個數為piles[i]。他的飼養員會離開h小時，這隻猴子需要在這段時間內把這n堆香蕉都吃完。他吃香蕉的速度是每小時可以從每堆中吃k根香蕉，如果在一小時內吃完，他不會移動到下一堆。請問這隻猴子想要用最慢的速度k在h小時內吃完香蕉，k是多少。

Example1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

第三型是保留binary search的程式結構，但是從對於計算某個資料結構特定的index改成根據題目的邏輯去搜尋一段數字的區間。
模板變成：

def binarySearch(low, high):

    while low <= high:
        mid = (low + high) // 2

        if isCorrect(mid) > 0:
            high = mid - 1
        elif isCorrect(mid) < 0:
            low = mid + 1
        else:
            return mid
    return -1

分析：本題的猴子以最快的速度吃完香蕉的話，他的速度必須是一小時內吃完最多數量的香蕉堆（比這個數量多也沒用，因為他還是會等到一個小時到了，才去吃下一堆）；而最慢的可能速度是一個小時只吃一根。
我們要在這段區間內去確定，哪些速度是合理的，並且因為要找出合理且最慢的速度，要讓右指標向左移。

import math
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)

        while l <= r:
            m = (l + r) // 2
            time = 0
            for n in piles:
                time += math.ceil(n / m)
            
            if time > h:
                l = m + 1
            else:
                r = m - 1
            
        return l

明天繼續Binary Search的進階題