---
# System prepended metadata

title: '**程式筆記(binary search)**'
tags: [binary search, code, note]

---

# **程式筆記(binary search)**


:::info
:information_source: 日期 : 2023/12/10
:::



**:thumbsup:** 模板

* [模板好文](https://haogroot.com/2021/01/26/binary-search-templateii_leetcode/)

* 模板1 (經典binary search)
binary search 結束後並不會收斂出任何元素
適用於input array 一定包含 target 且 target 只存在一個
```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (right + left) // 2
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid # 最後會是回傳mid
```
```
停止條件 : left > right
```

* 模板2 (進階binary search)
也可以用模板1變形實作
binary search 結束最後會收斂得到一個元素，代表 binary search 過程中，區間內至少會有 2 個元素
題目 : Find Peak Element / Koko Eating Bananas
```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = (right + left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        
        return l or r
```
```
停止條件 : left == right
往左找: right = mid (此時不會exclude right作為正確答案)
往右找: left = mid+1
```


---


**:thumbsup:** binary search 模板1

* Search a 2D Matrix
找列規則 : 比這列的最左邊還小 or 比這列的最右邊還大 -> 換列
```python
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        t, d = 0, len(matrix) - 1
        while t <= d:
            mid = (t + d) // 2
            if matrix[mid][0] > target:
                d = mid - 1
            elif matrix[mid][-1] < target:
                t = mid + 1
            else:
                break
        
        l, r = 0, len(matrix[0]) - 1
        while l <= r:
            mid1 = (l + r) // 2
            if matrix[mid][mid1] < target:
                l = mid1 + 1
            elif matrix[mid][mid1] > target:
                r = mid1 - 1
            else:
                return True
        
        return False
```

**無條件捨去
回傳r**

* Time Based Key-Value Store 找小的timestamp
```
Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]
```
```
record["foo"] = [["bar", 1], ["bar2", 4]]
如果給3，無條件捨去法，需要回傳1 bar
```


```python 
class TimeMap:

    def __init__(self):
        self.record = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.record[key].append([value, timestamp])
    
    def get(self, key: str, timestamp: int) -> str:
        val_l = self.record[key]
        l, r = 0, len(val_l) - 1
        while l <= r:
            mid = (l + r) // 2
            if val_l[mid][1] < timestamp:
                l = mid + 1
            elif val_l[mid][1] > timestamp:
                r = mid - 1
            else:
                return val_l[mid][0]

        return val_l[r][0]
```


* Sqrt(x)
```
ex. 求10的平方根
l, r = 0, 10
mid = ⌈(0+10)÷2⌉ = 5
10 < 25, r = 4
mid = ⌈(0+4)÷2⌉ = 2
10 > 4, l = 3
mid = ⌈(3+4)÷2⌉ = 3
10 > 9, l = 4
mid = ⌈(4+4)÷2⌉ = 4
10 < 16, r = 3
```

```python
class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x

        while l <= r:
            mid = (l + r) // 2
            if x < mid * mid:
                r = mid - 1
            elif mid * mid < x:
                l = mid + 1
            else:
                return mid
        
        return r # round down
```

**要無條件進位
回傳l**

* Search Insert Position

```
Input: nums = [1,3,5,6], target = 7
Output: 4 (index)
```

```python
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] < target:
                l = mid + 1
            elif nums[mid] > target:
                r = mid - 1
            else:
                return mid
        
        return l # round up
```



**:thumbsup:** binary search 模板2

* Koko Eating Bananas
```
Input: piles = [3,6,7,11], h = 8
Output: 4
```

```python
# 模板2

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

        while l < r:
            speed = (l + r) // 2
            temp_h = 0
            for p in piles:
                temp_h += math.ceil(p / speed)
            if temp_h > h:
                l = speed + 1
            elif temp_h <= h:
                r = speed
            
        return l or r
```

```python
# 模板1 - 無條件進位

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

        while l <= r:
            speed = (l + r) // 2
            temp_h = 0
            for p in piles:
                temp_h += math.ceil(p / speed)
            if temp_h > h:
                l = speed + 1
            # 仍有可能找到speed更小但temp_h相同的答案
            # speed 和 temp_h 不是一對一
            elif temp_h <= h: 
                r = speed - 1
            
        return l # round up
```


* Find Peak Element
如果 mid 小於 mid + 1(左小右大)，這代表我們更有可能在 mid右側找到一個更大的元素，這樣的元素更可能是峰值
```python
# 模板2

class Solution(object):
    def findPeakElement(self, nums):
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) // 2
            if nums[mid] > nums[mid + 1]: 
                r = mid # mid可能真的為peak
            else: 
                l = mid + 1 
        return l
```

```python
# 模板1 - 只和鄰居比較

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)
        l, r = 0, n - 1

        while l <= r:
            mid = (l + r) // 2
            if mid - 1 >= 0 and nums[mid - 1] > nums[mid]:
                r = mid - 1
            elif mid + 1 < n and nums[mid] < nums[mid + 1]:
                l = mid + 1
            else:
                return mid
        
        return -1
```


* Successful Pairs of Spells and Potions
```
給定三值spells = [5,1,3], potions = [1,2,3,4,5], success = 7
第一輪 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]，回傳4，因為10,15,20,25比7還大
```

```python
# 模板1 - 無條件進位

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        n = len(potions)
        res = []
        potions_sort = sorted(potions)

        for s in spells:
            l, r = 0, n - 1
            index = self.binary_search_round_up(l, r, s, potions_sort, success)
            res.append(n - index)
        
        return res
    
    # round up
    def binary_search_round_up(self, l, r, s, potions_sort, success):
        while l <= r:
            mid = (l + r) // 2
            if s * potions_sort[mid] >= success:
                r = mid - 1
            else:
                l = mid + 1
        return l  
```


---

**:thumbsup:** Rotated Sorted array

* Find Minimum in Rotated Sorted Array(在Rotated Sorted的array找到最小值)
    1. 如果l的數字小於r的數字 (例如[0,1,2,3,4,5,6])-> 符合常規的排列 -> 值回傳最小值l
    2. 如果l的數字大於r的數字 例如[6,5,3,4,0,1,2])-> 不符合常規的排列，當在這個情況底下時 -> 用mid和r的大小來判斷異常區在哪(左邊還是右邊)，最後l和r兩個數會差1，並且異常值會在r上面

```python   
# 模板1

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        res = float("inf")
        while l <= r:
            mid = (l + r) // 2 
            if nums[r] < nums[mid]:
                l = mid + 1
            else:
                res = min(res, nums[mid])
                r = mid - 1

        return res
```

```python
# 模板2

class Solution:
    def fclindMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            mid = (l + r) // 2
            if nums[mid] < nums[r]:
                r = mid # mid可能真的為smallest
            else:
                l = mid + 1
        
        return nums[l]
```


* Search in Rotated Sorted Array (在Rotated Sorted的array找數字)
剛開始，必定左邊和右邊會有一邊為sorted
如果是左邊，只有nums[l] <= target < nums[mid]需要往左找，剩下都是往右找
如果是右邊，只有nums[mid] < target <= nums[r]需要往右找，剩下都是往左找

先處理變異區，步步逼近到mid的位置就是target，先進行大分區，舉例區說明
    1. 當mid > l -> 2345601 -> 先處理最奇怪的區域(234)，要小於mid大於l，剩下照常理分區(一個條件即可)
    2. 當mid < l -> 5601234 -> 先處理最奇怪的區域(234)，要大於mid小於r，剩下照常理分區(一個條件即可)
```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            
            if target == nums[mid]:
                return mid

            # 4,5,6,7,0,1,2
            # left sorted
            if nums[mid] >= nums[l]:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                elif target < nums[l]:
                    l = mid + 1
                elif target > nums[mid]:
                    l = mid + 1
            
            # 5,6,0,1,2,3,4
            # right sorted
            else:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                elif target > nums[r]:
                    r = mid - 1
                elif target < nums[mid]:
                    r = mid - 1
        
        return -1
``` 


* Search in Rotated Sorted Array II
和Search in Rotated Sorted Array差不多，只是有重複數字，導致無法判定左右側哪邊有序時，
```
nums = [2, 2, 2, 3, 2, 2] # 左有序
        l    mid       r
nums = [2, 2, 2, 0, 1, 2] # 右有序
        l    mid       r
```
用l + 1 or r - 1去跳過重複區域，重新定位mid
```python
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if target == nums[mid]:
                return True
            
	     # 多這裡
            if nums[l] == nums[mid]:
                l += 1
                continue
	     # 擇一
            # if nums[r] == nums[mid]:
            #     r -= 1
            #     continue

            # 4,5,6,7,0,1,2
            # left sorted
            if nums[mid] >= nums[l]:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                elif target < nums[l]:
                    l = mid + 1
                elif target > nums[mid]:
                    l = mid + 1
            
            # 5,6,0,1,2,3,4
            # right sorted
            else:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                elif target > nums[r]:
                    r = mid - 1
                elif target < nums[mid]:
                    r = mid - 1  
        
        return False
```




**:thumbsup:** Sorted array找邊界/中點


* Find First and Last Position of Element in Sorted Array
給定nums = [5,7,7,8,8,10], target = 8，求target左右邊界，意識到要處理[8, 8, 8], [8, 8, 10], [8, 9, 10]等情況，如果找左邊界，那就不停用r逼近，直到l>r，如果找右邊界(例如此範例)，那就不停用l逼近，直到l>r

```python
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        res_l, res_r = -1, -1
        res_l = self.binary_search_find_left(nums, target, True)
        res_r = self.binary_search_find_left(nums, target, False)
        return [res_l, res_r]

    def binary_search_find_left(self, nums, target, findLeft):
        l, r = 0, len(nums) - 1
        res = -1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            else: # nums[mid] == target
                res = mid
                if findLeft:
                    r = mid - 1
                else:
                    l = mid + 1
        
        return res
```

* Median of Two Sorted Arrays (找兩sorted array的中間值)
先找兩個list中最小list的一半(mid1)，再用全部長度的一半減mid1得到mid2
接著用兩個mid分別得到各自list中的左右(l1,l2,r1,r2)，當l1<r1 and l2<r1時滿足條件，即可根據奇偶數輸出，若不滿足條件，則可以把mid1左右修正
```python
l, r = 0, len(nums1) - 1
while True:
    mid1 = (l + r) // 2 # 短的長度的一半
    mid2 = half - mid1 - 2 # 2是兩個index對於長度的修正

    # 有條件的
    l1 = nums1[mid1] if 0 <= mid1 else float("-inf")
    r1 = nums1[mid1 + 1] if mid1 + 1 < len(nums1) else float("inf")
    l2 = nums2[mid2] if 0 <= mid2 else float("-inf")
    r2 = nums2[mid2 + 1] if mid2 + 1 < len(nums2) else float("inf")

    if l1 <= r2 and l2 <= r1:
        if total % 2:
            return min(r1, r2)
        else:
            return (max(l1, l2) + min(r1, r2)) / 2
    # 對mid1修正 因為上面會隨之調整mid2 
    elif l1 > r2: # l1太大
        r = mid1 - 1
    elif l2 > r1: # l2太大 r1太小
        l = mid1 + 1
```

---

**:thumbsup:** binary 變形

* Minimize the Maximum Difference of Pairs
用binary先去找可能的差值，用那個差值去看是否可以蒐集到p個pair，如果可以則往更小的差值找，如果不行則往更大的差值找，慢慢逼近
```python
class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        # valid : retrun p pairs of answer
        def valid(thershold):
            count = 0
            i = 0
            while i < len(nums) - 1:
                if abs(nums[i] - nums[i + 1]) <= thershold:
                    count += 1
                    i += 2
                else:
                    i += 1
                if count == p:
                    return True
            return False
        
        nums.sort()

        res = 0
        # choosing the thershold
        l, r = 0, 10 ** 9
        while l <= r:
            mid = l + (r - l) // 2 # (l + r) // 2
            if valid(mid):
                res = mid
                r = mid - 1
            else: # mid is too small
                l = mid + 1

        return res
```

* Search a 2D Matrix II
![image](https://hackmd.io/_uploads/rJOsoLly1x.png =30%x)

這題解法精妙，從最左下角開始，如果target比較大，就往右邊column找，如果target比較小，就往下一排row找。其實數字本身的左邊跟下面都會比較小，但因為是從最左下角找到最右上角，所以左邊必定已經被確認過不符合
```python
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n, m = len(matrix), len(matrix[0])
        r, c = n - 1, 0

        while r >= 0 and c < m:
            if matrix[r][c] < target:
                c += 1
            elif matrix[r][c] > target:
                r -= 1
            else:
                return True

        return False
```

---






**講解連結**
https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-search-2.md
Provided by. 

###### tags: `binary search` `note` `code`