# binary search, summary
###### tags: `interview` `binary search`

important ref: https://ojeveryday.github.io/AlgoWiki/#/BinarySearch/README?id=%e4%ba%8c%e5%88%86%e6%9f%a5%e6%89%be%e6%a8%a1%e6%9d%bf%e4%ba%8c%ef%bc%88%e6%8e%a8%e8%8d%90%ef%bc%89

先寫if-else，再決定中間數是否上取整；
在使用多了以後，就很容易記住，只要看到 left = mid ，它對應的取中位數的取法一定是 int mid = left + (right - left + 1) / 2;。

核心思想：雖然模板有兩個，但是核心思想只有一個，那就是：把待搜索的目標ele放在最後判斷，每一次循環排除掉不存在目標元素的區間，目的依然是確定下一輪搜索的區間；

特徵：while (left < right)，這裡使用嚴格小於 < 表示的臨界條件是：當區間裡的元素只有 2 個時，依然可以執行循環體。換句話說，退出循環的時候一定有 left == right 成立，這一點在定位元素下標的時候極其有用；

在循環體中，先考慮 nums[mid] 在滿足什麼條件下不是目標元素，進而考慮兩個區間 [left, mid - 1] 以及 [mid + 1, right] 裡元素的性質，目的依然是確定下一輪搜索的區間；

注意 1：先考慮什麼時候不是解，確定下一輪搜索的區間，它的反面（也就是 else 語句的部分），直接從上一個分支的反面區間得到；

根據邊界情況，看取中間數的時候是否需要上取整；

在退出循環以後，根據情況看是否需要對下標為 left 或者 right 的元素進行單獨判斷，這一步叫「後處理」。在有些問題中，排除掉所有不符合要求的元素以後，剩下的那 1 個元素就一定是目標元素，可以直接返回 left（或者 right）。

:::success
while 不等於
回傳左右皆可

向右找 上高斯
向左找 下高斯
保持T
排除F
:::
## find rightmost valid element
Find the right-most T.
If it is a T, all LHS will also be T's.

0 1 2 3 4 5 6 7 8
T T T T T T T T T ==>  8
T T T T T T T T F ==>  7
T T F F F F F F F ==>  1
T F F F F F F F F ==>  0
F F F F F F F F F ==> -1 // no T at all

related problem:
https://hackmd.io/@y56/BJXStesvY
// find largest has_dup()==True

def find_rightmost_T(li):
    if not li:  # check special case
        return -1

    if li[0] != 'T':  # check special case
        return -1  # no T at all

    # now, sure to have at least one T
    left = 0
    right = len(li) - 1
    while left < right: # break at l == r; always use this kind of condition!
        mid = (left + right) // 2 + 1 
        # !!! bc we want rightmost; use ceil() to RHS !!!
        if li[mid] == 'T':
            left = mid
            # want rightmost T, mid here is T, all LHS guys are T and no longer under consideration
            # nonsense for left=mid-1 since we are ignoring LHS
            # nonsense for left=mid+1, maybe this mid is the rightmost; note that we will return left(same as right), if we do left=mid+1 we are ignoring the ans
        else:  # F
            right = mid - 1
            # nonsense for right=mid, note that we will return left(same as right, will be a T); we can't achieve so by keeping an F at right
            # nonsense for right=mid+1; want rightmost T, mid here is F, all RHS guys are F and no longer under consideration
    return left  # same as right

print(find_rightmost_T('TTTT'))
print(find_rightmost_T('TTTF'))
print(find_rightmost_T('TTFF'))
print(find_rightmost_T('TFFF'))
print(find_rightmost_T('FFFF'))

print(find_rightmost_T('TTTTT'))
print(find_rightmost_T('TTTTF'))
print(find_rightmost_T('TTTFF'))
print(find_rightmost_T('TTFFF'))
print(find_rightmost_T('TFFFF'))
print(find_rightmost_T('FFFFF'))

## find leftmost valid element

Find the left-most T.
If it is a T, all RHS will also be T's.

0 1 2 3 4 5 6 7 8
T T T T T T T T T ==>  0
F T T T T T T T T ==>  1
F F T T T T T T T ==>  2
F F F F F F F T T ==>  7
F F F F F F F F T ==>  8
F F F F F F F F F ==> -1

related problem:
https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/

def find_leftmost_T(li):
    if not li:  # check special case
        return -1

    if li[-1] != 'T':  # check special case
        return -1  # no T at all

    # now, sure to have at least one T
    left = 0
    right = len(li) - 1
    while left < right: # break at l == r; always use this kind of condition!
        mid = (left + right) // 2
        # !!! bc we want leftmost; use floot() to go LHS !!!
        if li[mid] == 'T':
            right = mid  
            # want leftmost T, mid here is T, all RHS guys are T and no longer under consideration
            # nonsense for right=mid+1 since we are ignoring RHS
            # nonsense for right=mid-1, maybe this mid is the leftmost; note that we will return left(same as right), if we do right=mid-1 we are ignoring the ans
            
        else:  # F
            left = mid + 1
            # nonsense for left=mid, note that we will return left(same as right, will be a T); we can't achieve so by keeping an F at left 
            # nonsense for left=mid-1; want leftmost T, mid here is F, all LHS guys are F and no longer under consideration
    return left  # same as right

print(find_leftmost_T('TTTT'))
print(find_leftmost_T('FTTT'))
print(find_leftmost_T('FFTT'))
print(find_leftmost_T('FFFT'))
print(find_leftmost_T('FFFF'))

print(find_leftmost_T('TTTTT'))
print(find_leftmost_T('FTTTT'))
print(find_leftmost_T('FFTTT'))
print(find_leftmost_T('FFFTT'))
print(find_leftmost_T('FFFFT'))
print(find_leftmost_T('FFFFF'))