Binary Method 二分法

2021.12.24
Algorithm Binary Method / Divide and Conquer

分治法 Divide and Conquer

總是能夠將「問題 X 」拆分為「問題 A 」和「問題 B 」
滿足「問題 A 」+「問題 B 」=「問題 X 」
且能確定「問題 X 」的解只存在於「問題 A 」或「問題 B 」兩者其中之一

如果「問題 X 」的 brute force 解法之 time complexity 為 O(n)
則使用 binary method 的時間複雜度將減少為 O(log(n))

注意要小心演算法是否每個範圍內的數都會被遍歷！

Template

Strictly Increasing

Pattern: while left <= right

left, right = bound_left, bound_right
while left <= right:
  mid = (left + right) // 2
  num = array[mid]
  if is_satisfied(num, target) == "not enough" / you need to adjust left:
    left = mid + 1
  elif is_satisfied(num, target) == "too many" / you need to adjust right:
    right = mid - 1
  else: return mid
return None

Pattern: while left < right ≡ Duplicate Elements, Left-Most Insertion Point

left, right = bound_left, bound_right
while left < right: # Leave when left == right
  mid = (left + right) // 2
  num = array[mid]
  if is_satisfied(num, target) == "not enough" / you need to adjust left:
    left = mid + 1 
  elif is_satisfied(num, target) == "too many" / you need to adjust right:
    right = mid
return left # left == middle == right

Duplicate Elements

The point is the position where or is_satisfied(mid, target) == "satisfied" is.

Left-Most Insertion Point

回傳的i
s.t. is_satisfied(i - 1, target) == "not enough"
and (is_satisfied(i, target) == "too many" or is_satisfied(i - 1, target) == "satisfied")

left, right = bound_left, bound_right + 1
while left < right:
  mid = (left + right) // 2
  num = array[mid]
  if is_satisfied(num, target) == "not enough":
    left = mid + 1 
  elif is_satisfied(num, target) == "too many" or is_satisfied(mid, target) == "satisfied":
    right = mid
return left

Right-Most Insertion Point

回傳的i
s.t. (is_satisfied(i - 1, target) == "not enough" or is_satisfied(i - 1, target) == "satisfied")
and is_satisfied(i, target) == "too many"

left, right = bound_left, bound_right + 1
while left < right:
  mid = (left + right) // 2
  num = array[mid]
  if is_satisfied(num, target) == "not enough" or is_satisfied(mid, target) == "satisfied":
    left = mid + 1 
  elif is_satisfied(num, target) == "too many":
    right = mid
return left

Binary Search

Python 可以使用 bisect

def find_i(nums, num, left=0, right=-1):
  right = (right + len(nums)) % len(nums)
  while left < right:
    mid = (left + right) // 2
    if nums[mid] < num: left = mid + 1 
    else: right = mid
  return left

非整數形式的二分法

範例

Pramp – Root of Number

Solution

def root(x,n):
  l, r = 0, x
  while r - l > 0.001:
    rt = float(l + r) / 2
    rt_to_the_nth_power = rt ** n
    if rt_to_the_nth_power > x:
      r = rt
    elif rt_to_the_nth_power < x:
      l = rt
    else:
      return rt
  return round(rt, 3)

經典例題

Leetcode # 704. Binary Search

注意迴圈停止的條件
當 nums 內只有一元素時
若 while 的條件為 while left < right:
會導致不進入迴圈直接回傳 -1 結束
注意更新左右邊界的方式
如上所述，當 left 為 right – 1 時，cur 會等於 left
此時若 target 大於 nums[cur] 且左邊界的更新條件為 left = cur
會造成 left 永遠等於 cur 無法更新，導致無窮迴圈

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