以從開頭逐一比較的線性搜尋，在存有100個不同值的陣列中尋找目標值。若目標值一定在陣列中，且位於各位置的機率相等，則比較次數的平均為多少？

正確答案：B. 50.5次

目標值在第 k 個位置時要比較 k 次，因此平均為 (1 + 2 + … + 100) / 100 = 50.5次，一般而言為 (n + 1)/2 次。最佳情況（位於開頭）為1次，最差情況（位於末尾）為100次，平均與最差都與 n 成正比，因此時間複雜度為 O(n)。約7次相當於 log₂ 100 ≈ 6.6，是二分搜尋的次數，但資料未排序時無法使用。

• A. 這接近二分搜尋的最多次數，不是線性搜尋的平均。
• B. 正確。(1 + 2 + … + 100)/100 = 50.5次，一般為 (n + 1)/2 次。
• C. 這是最差情況（目標值在末尾）的次數。