0

# python 二分搜索絕招

``````def binary_search(array) -> int:
left, right = 0, len(array)
while left < right:
mid = left + (right - left) // 2
if mid 滿足某條件:
right = mid
else:
left = mid + 1
return left
``````

left, right設定答案的範圍可能落在區間[left, right)中，

left會是第一個滿足條件的值

1. left, right的範圍，需涵蓋可能的答案
2. 視需求而定決定要回傳「left」還是「left-1」(left-1是最後一個不滿足條件的值)
3. 決定「某條件」是什麼，這部分最傷腦筋

# 練功囉

``````Given n = 5, and version = 4 is the first bad version.

Then 4 is the first bad version.
``````

``````# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer

class Solution:
left, right = 1, n
while left < right:
mid = left + (right - left) // 2
right = mid
else:
left = mid + 1
return left
``````

``````Input: [1,3,5,6], 0
Output: 0

Input: [1,3,5,6], 2
Output: 1

Input: [1,3,5,6], 5
Output: 2

Input: [1,3,5,6], 7
Output: 4
``````

``````class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left
``````

``````class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= nums[-1]:
right = mid
else:
left = mid + 1
return nums[left]
``````

(類似題: 1283. Find the Smallest Divisor Given a Threshold)

``````class Solution:
def minEatingSpeed(self, piles: List[int], H: int) -> int:
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
if sum([ceil(p/mid) for p in piles])<=H:
right = mid
else:
left = mid + 1
return left
``````

``````# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
def findPeak(self)-> int:
left, right = 1, self.length-1
while left < right:
mid = left + (right - left) // 2
if self.get(mid-1)>self.get(mid)>self.get(mid+1):
right = mid
else:
left = mid + 1
return left-1

def search_inc(self, target, left, right):
while left < right:
mid = left + (right - left) // 2
if self.get(mid)>=target:
right = mid
else:
left = mid + 1
return left if left<self.length and self.get(left)==target else -1

def search_desc(self, target, left, right):
while left < right:
mid = left + (right - left) // 2
if self.get(mid)<=target:
right = mid
else:
left = mid + 1
return left if left<self.length and self.get(left)==target else -1

def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
self.length = mountain_arr.length()
self.get = mountain_arr.get # 名稱太長，取個別名
peak = self.findPeak() # 山峰的index
left_search = self.search_inc(target,0,peak)
if left_search!=-1:
return left_search
return self.search_desc(target,peak, self.length)
``````

# 挑戰題(可能很難想到這也能用二分搜索)

``````Input: [0,1,3,5,6]
Output: 3

``````

index 26後面有「95-26=69」個數字，

``````class Solution:
def hIndex(self, citations: List[int]) -> int:
left, right = 0, len(citations)
while left < right:
mid = left + (right - left) // 2
if citations[mid] >= len(citations)-mid:
right = mid
else:
left = mid + 1
return len(citations)-left
``````

(類似題: 1011. Capacity To Ship Packages Within D Days)

• `m = 1`，子陣列就是原來的陣列，答案就是`sum(nums)`
• `m = len(nums)`，每個子陣列僅一個元素，答案就是`max(nums)`

``````class Solution:
#函數意義: 是否有辦法將nums切成m塊子陣列，每塊的最大值不超過ubd
def can_split(self, nums, m, ubd):
part, curSum = 1, 0
for num in nums:
curSum += num
if curSum > ubd:
curSum = num
part+=1
if part > m:
return False;
return True

def splitArray(self, nums: List[int], m: int) -> int:
left, right = max(nums), sum(nums)
while left < right:
mid = left + (right - left) // 2
if self.can_split(nums, m, mid):
right = mid
else:
left = mid + 1
return left
``````

``````Input: nums = [1,2,3,4,5,6,7,8,9,10], m = 5
Output: 15

[1,2,3,4,5], [6,7], [8], [9], [10]，

``````

``````Input: m = 3, n = 3, k = 5
Output:
Explanation:
The Multiplication Table:
1	2	3
2	4	6
3	6	9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).
``````

k也可能很大，

``````1	2	3
2	4	6
3	6	9
``````

``````class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
left, right = 1, n * m
while left < right:
mid = left + (right - left) // 2
# 檢查在乘法表裡面是否有至少k個數小於等於num
if sum(min(mid // v, n) for v in range(1, m + 1))>=k:
right = mid
else:
left = mid + 1
return left
``````

``````Input:
nums = [1,3,1]
k = 1
Output: 0

(1,3) -> 2
(1,1) -> 0
(3,1) -> 2

``````

``````class Solution:

# 判斷是否至少有k個數對的距離小於等於distance
def enough(self, distance, nums, k) -> bool:  # two pointers
count, i, j = 0, 0, 0
while i < len(nums) or j < len(nums):
while j < len(nums) and nums[j] - nums[i] <= distance:  # move fast pointer
j += 1
count += j - i - 1  # count pairs
i += 1  # move slow pointer
return count >= k

def smallestDistancePair(self, nums: List[int], k: int) -> int:
nums.sort()
left, right = 0, nums[-1] - nums[0]
while left < right:
mid = left + (right - left) // 2
if self.enough(mid, nums, k):
right = mid
else:
left = mid + 1
return left
``````