# Binary Search

t = 6
data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# 若拿掉6，找不到目標會掉進無窮迴圈 不斷輸出4 5 4
# 若拿掉5, 6則不斷輸出3 4 3

l = 0
r = len(data)
m = 0
while l < r:
    last_m = m
    m = (l + r) // 2
    print(l, r, m)
    if data[m] == t:
        print("找到t index=", m)
        break
    elif data[m] > t:
        print("r=m")
        r = m
    elif data[m] < t:
        print("l=m")
        l = m