iPAS 備考專區 登入

iPAS AI 應用規劃師 初級 科目一 人工智慧基礎概論・115 年第一次・L11・第 18 題

二分搜尋找 27 需要比較幾次?

原題

某電商平台工程師需在已排序的價格清單中,快速定位指定價格是否存在,給定排序後陣列:arr = [3, 8, 14, 19, 21, 27, 33, 45, 52]。若搜尋目標值為 27,且採用標準二分搜尋(Binary Search)流程(每次比較後排除中位數),請問最多需要比較幾次即可找到目標?

白話

某電商平台工程師要在一個已排序的價格清單中,快速定位指定價格是否存在。清單共 9 個元素:[3, 8, 14, 19, 21, 27, 33, 45, 52],目標是找到 27。工程師採用標準二分搜尋(Binary Search)流程,規則是每次比較後排除中位數。

問你:按照這個流程,最多需要比較幾次才能找到 27?

一句話總結

在陣列 [3, 8, 14, 19, 21, 27, 33, 45, 52] 中用二分搜尋找 27,依序比較 21(第 1 次)→ 33(第 2 次)→ 27(第 3 次),共需 3 次比較。

情境

先感受問題:你玩過「猜數字 1 到 100」嗎?

「猜數字」遊戲:我心裡想一個 1 到 100 的數字,你每次猜一個,我只告訴你「猜太大」、「猜太小」或「猜對了」。

聰明的猜法是每次猜中間值:先猜 50,太大就猜 25,太小就猜 75,這樣每次都把範圍砍半,最多 7 次就能猜到 1 到 100 裡的任何數字。

「台灣快購」電商平台工程師陳建廷面對的就是同樣的問題:商品價格清單已排序好,每次查詢要最快判斷某個價格存在不存在。二分搜尋的邏輯和猜數字完全一樣,每次從中間比對,縮小一半範圍。

舊方法

如果不用二分搜尋,從頭搜到尾有多慢

陳建廷的同事小李不知道二分搜尋,每次都用「線性搜尋」從第一個找起:

  1. 比較 arr[0]=3:3 ≠ 27,繼續
  2. 比較 arr[1]=8:8 ≠ 27,繼續
  3. 比較 arr[2]=14:14 ≠ 27,繼續
  4. 比較 arr[3]=19:19 ≠ 27,繼續
  5. 比較 arr[4]=21,再比較 arr[5]=27:21 ≠ 27 繼續;27 = 27,找到了!共比較了 6 次。

9 個元素找第 6 個,線性搜尋要 6 次。如果清單有 100 萬個價格,最壞情況要比 100 萬次。二分搜尋呢?100 萬個元素最多只需 20 次。

新方法

二分搜尋一步一步走:找 27

陣列(索引從 0 到 8):[3, 8, 14, 19, 21, 27, 33, 45, 52]

第 1 次比較:搜尋範圍 [0, 8],中位數索引 = (0+8)÷2 = 4,arr[4] = 21。目標 27 > 21,所以排除左半邊(含中位數),新範圍 [5, 8]。

第 2 次比較:搜尋範圍 [5, 8],中位數索引 = (5+8)÷2 = 6(取整),arr[6] = 33。目標 27 < 33,所以排除右半邊(含中位數),新範圍 [5, 5]。

第 3 次比較:搜尋範圍 [5, 5],中位數索引 = 5,arr[5] = 27。目標 27 = 27,找到了!

總共比較了 3 次。注意題目說「每次比較後排除中位數」,所以找到中位數等於目標的那次,這次比較也算一次,答案是 3 次。

這就是選項 B 的正確答案:二分搜尋在這個陣列中找 27,最多需要 3 次比較。

錯選項

為什麼其他選項是錯的

A2 次

字面在說什麼

說找到 27 只需要比較 2 次就夠。

為什麼不對

按照流程:第 1 次比較 arr[4]=21(範圍縮到 [5,8]),第 2 次比較 arr[6]=33(範圍縮到 [5,5]),還沒找到,必須進行第 3 次比較。2 次根本還沒找到答案,所以 A 不對。

誰會選錯

在第 2 次比較後,知道目標在 arr[5] 那個位置,就直接算「已知答案位置,不用再比」的人。但題目問的是「比較次數」,確認到 27 的那次比較也要算。

C4 次

字面在說什麼

說需要 4 次比較才能找到 27。

為什麼不對

第 3 次就找到了(arr[5] = 27),根本不需要第 4 次。可能是計算中位數時用了不同的公式(如向上取整),但標準二分搜尋 3 次就能找到。

誰會選錯

中位數索引計算錯誤的人。例如第 2 次範圍 [5,8],錯用 (5+8+1)÷2 = 7,arr[7]=45,再來 [5,6],再來 arr[5]=27,變成 4 次。正確的公式是 floor((left+right)/2)。

D5 次

字面在說什麼

說最多需要 5 次才能找到。

為什麼不對

9 個元素的陣列,log₂(9) ≈ 3.17,向上取整是 4 次(最壞情況)。3 次已經找到了,5 次超出合理範圍。選 D 代表對二分搜尋的效率完全沒有概念。

誰會選錯

完全沒有做計算,用「感覺應該要很多次」直覺選的人。

變形題

同個考點下次怎麼變形

延伸

想再往下看,這 5 個

答案、題目或解析有問題?回報這題

出處:iPAS 經濟部產業人才能力鑑定 ・ 115 年第一次 iPAS AI 應用規劃師 初級 科目一 人工智慧基礎概論 第 18 題

看官方原文 PDF

原題 © 經濟部產業發展署,AITerms.tw 僅作教學解析使用,本站解析以 CC BY-NC-SA 4.0 授權。