Day 10:經典的搜尋與排序

今天是階段三的最後一天,要學兩個經典中的經典:怎麼快速「找到」資料,以及怎麼把一堆資料「排好順序」。這是 13 天轉職甄試衝刺大綱的 Day 10。

📅 前言:找資料,原來也有聰明和笨的方法

昨天學到 O(log n) 比 O(n) 快很多,今天要學的二分搜尋,就是 O(log n) 最經典的例子。

⏳ 第 1～15 分鐘:二分搜尋(Binary Search)—— 猜數字遊戲

💡 生活比喻: 猜數字遊戲。假設答案是 1 到 100 之間的一個數字,對方只會回答「太大了」或「太小了」。最聰明的策略,不是從 1 開始一個一個猜,而是每次都猜中間值,再根據回答,把範圍砍半。

範例:答案是 73,範圍是 1～100

1. 猜 50(中間值)➔ 「太小了」➔ 範圍縮小成 51～100
2. 猜 75(新的中間值)➔ 「太大了」➔ 範圍縮小成 51～74
3. 猜 62 ➔ 「太小了」➔ 範圍縮小成 63～74
4. 猜 68 ➔ 「太小了」➔ 範圍縮小成 69～74
5. 猜 71 ➔ ... 依此類推,很快就會猜中 73

⚠️ 使用二分搜尋的前提:資料必須先排好順序! 如果電話簿沒有按照字母排序,你就沒辦法用「猜中間」的方式縮小範圍,因為你不知道答案在「比中間大」還是「比中間小」的那一半。

⏳ 第 16～25 分鐘:最簡單的排序概念

既然二分搜尋需要「資料先排好順序」,那資料本來沒排序時該怎麼辦?這就是排序演算法要解決的問題。

最直覺的排序方式(不要求你會寫程式,只要有概念):想像你手上拿到一疊亂序的撲克牌,你會怎麼把它們排好?常見的直覺做法是——每次都從剩下的牌裡,找出「最小的那張」,放到已經排好的那一堆的最後面,再繼續找下一個最小的,重複到排完為止。

💡 這種「每次找最小的放到後面」的做法,概念上跟選擇排序很像,雖然不是效率最好的排序法,但最直覺、最容易用生活例子理解。

⏳ 第 26～30 分鐘:小練習與解答

練習:用二分搜尋的邏輯,猜出 1～50 之間的答案「37」,寫出每一步猜測的過程

1. 猜 25(中間值)➔ 太小 ➔ 範圍變 26～50
2. 猜 38(新中間值)➔ 太大 ➔ 範圍變 26～37
3. 猜 31 ➔ 太小 ➔ 範圍變 32～37
4. 猜 34 ➔ 太小 ➔ 範圍變 35～37
5. 猜 36 ➔ 太小 ➔ 範圍變 37～37 ➔ 答案就是 37

只花了 5 次,就從 50 個可能裡找到答案——這就是 O(log n) 的威力。

🎯 目標

• 能說明二分搜尋「每次砍一半」的邏輯,並手動追蹤猜測過程
• 知道二分搜尋的前提是「資料必須先排序」