# **程式筆記(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
這題解法精妙，從最左下角開始，如果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`
Sign in with Wallet
Connect another wallet