公職◆資料結構題庫

【非選題】

一、給一個排序好的陣列（Sorted Array）A[low...high]，當我們要搜尋一個元素 X 是否在此陣列 A 中，二元搜尋法（Binary Search）是檢查陣列的中間位置的元素 A[next], next =

，和 X 做比較，並依比較結果作下列更新。

Case：

A[next]＝X：return

A[next]＞X：high <= next-1

A[next]＜X：low <= next +1

重複上述步驟搜尋更新的陣列 A[low...high]直到找到 X 或確認 X 不是在此陣列 A 中。若我們設計一個新的搜尋法來修改二元搜尋法，每次都是以下列方式選取 A[next]。 next←low+

其他步驟都和二元搜尋相同。請回答下列問題：（每小題 5 分，共 15 分）

【題組】新的搜尋法，在最差的情況下，它的執行時間複雜度為多少？原因為何？假設陣列 A 中有 n 個元素。