動機

Algorithm, Leetcode 101有提到binary search 可以當成 two pointer 的特別case，就來看看到底哪裡相關

丟掉哪些?

two pointer一次都只移動一格，一次只丟掉一個 binary search是一次移動一半，一次丟掉一半

two pointer

3sum

每做完一次2sum就丟掉一個最小的

def sum2(arr,target):
  i = 0
  j = len(arr)-1
  while i<j:
    if arr[i]+arr[j] == target:
      return True
    elif arr[i]+arr[j] > target:
      j -= 1
    else:
      i += 1
  return False

def sum3(arr,target):
  for i in range(len(arr)):
    if sum2(arr[i:],target-arr[i]):
      return True
  return False

一次丟一半

最大值最小化

注意，這裡的有序是廣義的有序，如果一個數組中的左側或者右側都滿足某一種條件，而另一側都不滿足這種條件，也可以看作是一種有序。

換言之，二分搜索法可以用來查找滿足某種條件的最大（最小）的值。 (lowerbound)

  • 答案在一個固定區間內；
  • 可能查找一個符合條件的值不是很容易，但是要求能比較容易地判斷某個值是否是符合條件的；
  • 可行解對於區間滿足一定的單調性。換言之，如果x是符合條件的，那麼有x+1或者x-1也符合條件。
    • （這樣下來就滿足了上面提到的單調性）

二分搜一個是找有沒有目標值，另一個是猜答案

通常會有一個函數去check答案是比目標大還是小，之後就是對答案的range做二分搜

basic

arr = [1,2,3]
i = 0
j = len(arr)
while i < j:
  mid = i+(j-i)//2
  if arr[mid] == target:
    return mid
  elif arr[mid] > target:
    j = mid
  else:
    i = mid+1
return False

雖然說一般常看到的bsearch都是只比中點，一般來說這樣也夠了，但其實應該這樣寫，才能比較靈活運用bsearch

arr = [1,2,3]
i = 0
j = len(arr)
while i < j:
  mid = i+(j-i)//2
  if arr[mid] == target:
    return mid
  elif arr[mid] < target <= arr[j-1]: # 在這個範圍才進去
    j = mid
  else:
    i = mid+1
return False

lower bound

lower_bound: 第一個 大於等於(不小於) target的位置

arr = [1,2,3]
i = 0
j = len(arr)
while i < j:
  mid = i+(j-i)//2
  if arr[mid] < target:
    i = mid+1
  else:
    j = mid
return False

upper bound

upper_bound: 第一個 大於 target的位置

arr = [1,2,3]
i = 0
j = len(arr)
while i < j:
  mid = i+(j-i)//2
  if arr[mid] < target:
    i = mid+1
  else:
    j = mid
return False

三分法

三分法可以用来查找凸函數的最大（小）值。

left ... lmid ... rmid ... right 如果lmid <= rmid，這樣極值一定不在lmid的左手邊(left ~ lmid)

如果lmid > rmid，這樣極值一定不在rmid的右手邊(rmid ~ right)

lmid = left + (right - left >> 1)
rmid = lmid + (right - lmid >> 1)  # 對右側區間取半
if (cal(lmid) > cal(rmid))
  right = rmid
else
  left = lmid

丟一半與丟一個: leetcode 154

array被rotate過，不過只要是有排序的range就可以放心地用binary search

因此第一件事是判斷現在是不是在有排序的range中，如果不是就只丟一個最左的 剩下就是binary search與遞迴會處理

def f(ns,l,r):
    if abs(l-r) <= 1:
        return min(ns[l],ns[r])
    else:
        mid = (l+r)//2
        if ns[l] < ns[mid]:
            if ns[mid] > ns[r]:
                return f(ns,mid+1,r)
            else:
                return f(ns,l,mid-1)
        elif ns[mid] < ns[r]:
            if ns[mid-1] < ns[r]:
                return f(ns,l,mid-1)
            else:
                return f(ns,mid,r)
        elif ns[l] == ns[mid]:
            return f(ns,l+1,r)
        else:
            return f(ns,l,r-1)
class Solution:
    def findMin(self, ns: List[int]) -> int:
        return f(ns,0,len(ns)-1)

leetcode 153

array被rotate過，但沒有重複，所以都是有排序的range，只要找出能用binary search就用，剩下遞迴

def f(ns,l,r):
    if abs(l-r) <= 1:
        return min(ns[l],ns[r])
    else:
        mid = (l+r)//2
        if ns[l] < ns[mid]:
            if ns[mid] > ns[r]:
                return f(ns,mid+1,r)
            else:
                return f(ns,l,mid-1)
        else:
            if ns[mid-1] < ns[r]:
                return f(ns,l,mid-1)
            else:
                return f(ns,mid,r)
class Solution:
    def findMin(self, ns: List[int]) -> int:
        return f(ns,0,len(ns)-1)

判圈演算法

def floyd(node):
  i = node
  j = node
  while i and j and j.next and i is not j:
    i = next(i)
    j = next(next(j))
  return i is j and j is not node

假設到loop前的長度是a，loop長為b i走了a+x*b+t，j走了a+y*b+t 其中j走的距離是i的兩倍，兩者相減，i == (y-x)*b

i是圈數的倍數，換言之，現在的i不管從哪邊走都是起點 所以，把其中一個放回起點，兩方開始一步一步走，相遇點就是起點

有起點找長度就簡單了，就是讓其中一方走到相遇就好

P.S.: linked list 的中點

這裡是利用1個走一倍1個走兩倍的特性，開始走得快的先到底，那麼走得慢的一定在中點

def mid(root):
  i = root
  j = root
  while j and j.next:
    i = next(i)
    j = next(next(j))
  return i