一、二元搜尋法（binary search）是用來從排序好的資料陣列中尋找資料。假設 n 筆資料
由小到大按照順序存在一維陣列 A 中，且每一筆資料長度一樣。
申論題內容
⑵設 f (n) 為二元搜尋法的執行時間，請分析 f (n) 和 n 的關係。提示：設 n=2k，
且每次搜尋的資料筆數為前次的一半。（15 分）
詳解 (共 1 筆)
詳解提供者：114年高考上榜
在搜索一個大小為 n 的數組時，最壞情況下需要進行多少次搜索操作呢？假設每次區間大小減半，那麼最壞情況下需要進行 k 次搜索操作，使得區間大小為 1。因此，最壞情況下，搜索一個大小為 n 的數組的時間複雜度為 O(k)。因為 n=2^k，所以 k=log n。因此，最壞情況下，搜索一個大小為 n 的數組的時間複雜度為 O(log n)。
阿摩線上測驗
登入