二元搜尋法

搜尋的值，與所有資料的中間值(中位數)做比對，必須先行排序。

若是有 n 筆資料，在最差的情況下，二分搜尋法總共需要比較 [log2n] + 1 次。

在數列 5,13,16,25,28,32,46,54 用二元搜尋法尋找46，會在第幾次比較中找到？

(A) 3

(B) 2

(C) 1

(D) 此數列無法使用二元搜尋法尋找

Ans: B

Python

#二分搜尋-必須是已排序數列，且任兩數不重複。

def binary_search(a,target):

  #設置選取範圍的指標

  low = 0 #左邊界

  upper = len(a) - 1 #右邊界

  i=0 #回合

  while low <= upper:

    mid = (low + upper) // 2 #取中間索引的值(除以2的商)

    print("第",i,"回合,左",low,",中",mid,"[",a[mid],"],右",upper,end='')

    #若target比中間的值大，將mid+1給左邊界，取右半

    if a[mid] < target:

      low = mid + 1

      print(",取右半")

    #若target比中間的值小，將mid-1給右邊界，取左半

    elif a[mid] > target:

      upper = mid - 1

      print(",取左半")

    #若target等於中間的值，則回傳

    else:

      print(",目標值")

      return mid

    i=i+1

  print("第",i,"回合,左",low,",中",mid,"[",a[mid],"],右",upper)

  return -1

a = list(map(int,input("輸入已排序數列：").split()))

target = int(input("尋找目標值："))

found = binary_search(a,target)

if found == -1:

  print("無法找到二元搜尋目標值",target)

else:

  print("發現二元搜尋目標值",target,",索引值為",found)