# 二元搜尋法

參考網站
https://ithelp.ithome.com.tw/articles/10213268

https://medium.com/appworks-school/binary-search-%E9%82%A3%E4%BA%9B%E8%97%8F%E5%9C%A8%E7%B4%B0%E7%AF%80%E8%A3%A1%E7%9A%84%E9%AD%94%E9%AC%BC-%E4%B8%80-%E5%9F%BA%E7%A4%8E%E4%BB%8B%E7%B4%B9-dd2cd804aee1
---

> 二元搜尋法前有個前提，來先排序，
> 如果還沒排序可用.sort() 來排序

!/usr/bin/env python3
# -*- coding: utf-8 -*-

def binary_search(data, key):
    low = 0
    high = len(data)-1
    while low <= high:
        mid = int((low + high) / 2)
        if key == data[mid]:
            return mid
        elif key > data[mid]:
            low = mid + 1
        else:
            high = mid - 1
    return -1

data = [1, 9, 2, 7, 4, 10, 3, 8, 5, 6]
key = 7
data.sort()
print(data)
ret = binary_search(data, key)
if ret == -1:
    print('找不到')
else:
    print('找到索引值' + str(ret))

## 觀念

a. [3, 5]: 閉區間，代表 3, 4, 5 （包含 3、5）

b. (4, 9): 開區間，代表 5, 6, 7, 8 （不包含 4、9）

c. [1, 6): 左閉右開區間，代表 1, 2, 3, 4, 5 （包含 1、卻不包含 6 )

>
>

## **問題**

1. 最上面的 while 迴圈裡面，為什麼我們要寫 left <= right，不能只寫 left < right 嗎？或說，當 left == right 時，需要繼續嗎？
2. right 的起始點為什麼是 array 的長度 -1，不能直接是 array 長度嗎？
3. 中間判斷邊界移動時，為什麼是 right = mid-1 跟 left = mid+1，如果不要 -1 跟 +1 或只有其中一邊+-1，會出錯嗎？

## **解答**

現在我們可以來回答上面三個問題了，問題的答案其實都是一樣的：因為我們定義的 left 與 right 是**閉區間**，也就是包含 left 端點與 right 端點。

問題 1 的答案：當我們 left == right 的那一刻，例如 left == 3、right == 3 好了，那代表可能答案會在 [3,3] 之間，這是個合理的區間，且區間裡只有 3 一個元素，所以當然要再跑一次，確定他是不是我們要的答案，因此 while 的判斷式會是 <= 而非 <。

問題 3 的答案：為什麼要 +-1，同理，因為我們要的答案是**閉區間**，假如 mid 不是答案(因為我們的if else 判斷式已經有一個是判斷是不是Mid==key 了，所以假設會走到另外兩個分支，則必定mid ≠key )，那 mid 必須被排除在**可能是答案的區間**裡，因此不需要再考慮他，直接用 [left, mid-1] 或 [mid+1, right] 當成新的區間即可。

問題 2 的答案：需要一點細心觀察，假如今天我們把 right 定義成 array 長度，也就是”最大的可能 index” + 1 的位置上，首先當然違反了閉區間的原則，因為”最大的可能 index” + 1 不可能是答案，不然就超出 array 範圍了。實際操作時，假如我們的 target 大於 array 裡面最大元素的值，例如 target = 11，我的左邊界就會不停的往右移動 mid+1, mid+1,…，最終他會跑到 left == right，且兩個都停在最大的 index +1，還記得 left == right 的時候我們要再跑一次，而此時 mid 的計算方式會讓我們得出 mid == left 的結果，最終我們的 nums[mid] 就會訪問一個超出範圍的位置，這顯然是很危險的，有些程式語言直接報錯，有的則會給你任意可能的回答，讓你以為沒問題，其實更加危險。