想在一堆資料裡找一個目標,最笨的辦法是從頭一個一個看到尾——就像在沒排序的名單裡找人,只能一行行掃。 但只要資料先按順序排好,你就能像查字典一樣:翻到中間、看目標落在前半還是後半,一次砍掉一半範圍, 沒幾步就逼近答案。想找得快,就得先付出「排序」這筆成本——這就是搜尋的核心取捨。 下面你可以挑不同方法、同挑一個目標,看它們各自各花了幾步找到(或確認找不到)。
這頁比較幾種「在一堆資料裡找目標」的方法。關鍵差別在前提:線性搜尋從頭找到尾,資料不用先排序,但慢; 二分搜尋每次砍一半,超快,但資料必須先排好序。你可以看到同樣找一個數字,各方法各花了幾步, 體會「先花力氣排序、之後才能用二分快速找」這個取捨。