![虛擬碼
? while (low < high)
mid = (low + high) / 2
if (a[mid] == n)
return mid
else if (a[mid] < n)
low = mid + 1
else if (a[mid] > n)
high = mid – 1
return a[low] == n ? low : -1](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-16-320.jpg)
![虛擬碼
? while (low < high)
mid = (low + high) / 2
if (a[mid] == n)
return mid
else if (a[mid] < n)
low = mid + 1
else if (a[mid] > n)
high = mid – 1
return a[low] == n ? low : -1
? 我看不懂虛擬碼 OAO！ （以前自學程式的我說）
? 不如我們這樣！ （看下頁）](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-17-320.jpg)
![虛擬碼 - 解說
? 當搜尋到
? low >= high 或是
? a[mid] = 想找的數字
? 就大功告成了！
1 3 4 6 8 9 10
highlow](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-27-320.jpg)
![虛擬碼 - 整合
? while (low < high)
mid = (low + high) / 2
if (a[mid] == n)
return mid
else if (a[mid] < n)
low = mid + 1
else if (a[mid] > n)
high = mid – 1
return a[low] == n ? low : -1
當 low < high 就繼續搜尋
low high
1 3 4 6 8 9 101 3 4 6 8 9 10](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-28-320.jpg)
![虛擬碼 - 整合
? while (low < high)
mid = (low + high) / 2
if (a[mid] == n)
return mid
else if (a[mid] < n)
low = mid + 1
else if (a[mid] > n)
high = mid – 1
return a[low] == n ? low : -1
1 3 4 6 8 9 103 4 6 8 9 10
low highmid
計算 mid (中點)](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-29-320.jpg)
![虛擬碼 - 整合
? while (low < high)
mid = (low + high) / 2
if (a[mid] == n)
return mid
else if (a[mid] < n)
low = mid + 1
else if (a[mid] > n)
high = mid – 1
return a[low] == n ? low : -1
如果 mid 上的數字就是目標，
傳回結果
low highmid
1 3 4 6 8 9 103 4 6 8 9 10](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-30-320.jpg)
![虛擬碼 - 整合
? while (low < high)
mid = (low + high) / 2
if (a[mid] == n)
return mid
else if (a[mid] < n)
low = mid + 1
else if (a[mid] > n)
high = mid – 1
return a[low] == n ? low : -1
如果目標應該在 右邊
就繼續在 右邊 搜尋
low highmid
1 3 4 6 8 9 103 4 6 8 9 10](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-31-320.jpg)
![虛擬碼 - 整合
? while (low < high)
mid = (low + high) / 2
if (a[mid] == n)
return mid
else if (a[mid] < n)
low = mid + 1
else if (a[mid] > n)
high = mid – 1
return a[low] == n ? low : -1
如果目標應該在 右邊
就繼續在 右邊 搜尋
high
1 3 4 8 9 103 4 6 8 9 10
low](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-32-320.jpg)
![1 3 4 6 8 9 10
虛擬碼 - 整合
? while (low < high)
mid = (low + high) / 2
if (a[mid] == n)
return mid
else if (a[mid] < n)
low = mid + 1
else if (a[mid] > n)
high = mid – 1
return a[low] == n ? low : -1
如果目標應該在 左邊
就繼續在 左邊 搜尋
low highmid](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-33-320.jpg)
![3 6 8 9 101 4
虛擬碼 - 整合
? while (low < high)
mid = (low + high) / 2
if (a[mid] == n)
return mid
else if (a[mid] < n)
low = mid + 1
else if (a[mid] > n)
high = mid – 1
return a[low] == n ? low : -1
如果目標應該在 左邊
就繼續在 左邊 搜尋
low high](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-34-320.jpg)
![3 6 8 9 101 4
虛擬碼 - 整合
? while (low < high)
mid = (low + high) / 2
if (a[mid] == n)
return mid
else if (a[mid] < n)
low = mid + 1
else if (a[mid] > n)
high = mid – 1
return a[low] == n ? low : -1
繼續從新的範圍搜尋
low high](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-35-320.jpg)
![3 6 8 9 101 4
虛擬碼 - 整合
? while (low < high)
mid = (low + high) / 2
if (a[mid] == n)
return mid
else if (a[mid] < n)
low = mid + 1
else if (a[mid] > n)
high = mid – 1
return a[low] == n ? low : -1
? 這樣應該能理解了吧 =D ？
繼續從新的範圍搜尋
low high](https://image.slidesharecdn.com/splittedbinarysearchandternarysearch-171222103948/85/Binary-Search-and-Ternary-Search-36-320.jpg)
Binary Search and Ternary Search
- 1. 關於二分搜尋及三分搜尋 On Binary Search and Ternary Search
- 2. 二分搜尋介紹 ? 單調數列找給定數字 0 1 2 3 4 5 6 1 3 4 6 8 9 10 1 3 4 6 8 9 10
- 3. 二分搜尋介紹 ? 單調數列找給定數字 0 1 2 3 4 5 6 1 3 4 6 8 9 10 1 3 4 6 8 9 10
- 4. 二分搜尋介紹 ? 單調數列找給定數字 ? 單調數列又代表什麼呢？ 0 1 2 3 4 5 6 1 3 4 6 8 9 10 1 3 4 6 8 9 10
- 5. 二分搜尋原理 ? 我們先來看這個 6 ? 這個 6 隱含了什麼訊息呢？ 1 3 4 6 8 9 103 4 6 8 9 10
- 6. 二分搜尋原理 ? 這個 6 告訴我們 ? 右邊 比較 大 1 3 4 6 8 9 103 4 6 8 9 10
- 7. 1 3 4 6 8 9 10 二分搜尋原理 ? 相反地 ? 左邊 比較 小 3 4 6 8 9 10
- 8. 二分搜尋原理 ? 所以 ? 如果想找 4 1 3 4 6 8 9 103 4 6 8 9 10
- 9. 二分搜尋原理 ? 所以 ? 如果想找 4 ? 4 會在 6 的 左邊 1 3 4 6 8 9 103 4 6 8 9 10
- 10. 二分搜尋原理 ? 繼續搜尋！ ? 所以我們現在 ? 可以看 左邊 就好 1 3 4 6 8 9 106 8 9 10
- 11. 二分搜尋原理 ? 同樣的方式 ? 我們看 3 (我們想找到 4 ) 3 6 8 9 101 4
- 12. 44 二分搜尋原理 ? 同樣地 31 6 8 9 10
- 13. 4 二分搜尋原理 ? 同樣地 ? 我也會知道 4 在 3 的 右邊 31 6 8 9 10
- 14. 二分搜尋原理 ? 於是我們就找到 4 了！ 1 3 4 6 8 9 10
- 15. 二分搜尋原理 ? 於是我們就找到 4 了！ ? 不斷 “戳” 點來看的這段過程，就是二分搜尋 1 3 4 6 8 9 10
- 16. 虛擬碼 ? while (low < high) mid = (low + high) / 2 if (a[mid] == n) return mid else if (a[mid] < n) low = mid + 1 else if (a[mid] > n) high = mid – 1 return a[low] == n ? low : -1
- 17. 虛擬碼 ? while (low < high) mid = (low + high) / 2 if (a[mid] == n) return mid else if (a[mid] < n) low = mid + 1 else if (a[mid] > n) high = mid – 1 return a[low] == n ? low : -1 ? 我看不懂虛擬碼 OAO！ （以前自學程式的我說） ? 不如我們這樣！ （看下頁）
- 18. 虛擬碼 - 解說 ? 我們需要兩個指標： 1 3 4 6 8 9 101 3 4 6 8 9 10
- 19. low (低) low 虛擬碼 - 解說 ? 我們需要兩個指標： high 1 3 4 6 8 9 101 3 4 6 8 9 10 high (低)
- 20. low 虛擬碼 - 解說 ? 這兩個指標代表 ? 目前搜尋的 範圍 low high 1 3 41 3 4 6 8 9 10
- 21. low 虛擬碼 -解說 ? 有了範圍 high 1 3 4 6 8 9 101 3 4 6 8 9 10
- 22. low 虛擬碼 -解說 ? 有了範圍 ? 接著，我們需要 挑 一個數字來看 high 1 3 4 6 8 9 101 3 4 6 8 9 10
- 23. low high 虛擬碼 -解說 ? 有了範圍 ? 接著，我們需要 挑 一個數字來看 ? 我們就挑 中間 這個吧！ mid mid (中) 1 3 4 6 8 9 103 4 6 8 9 10
- 24. high 虛擬碼 - 解說 ? 看到這邊是不是覺得很熟悉？ lowlow mid 1 3 4 6 8 9 103 4 6 8 9 10
- 25. high 虛擬碼 - 解說 ? 看到這邊是不是覺得很熟悉？ ? 沒錯！ 我們可以只看一邊 1 3 4 6 8 9 106 8 9 10 lowlow mid
- 26. 虛擬碼 - 解說 ? 看到這邊是不是覺得很熟悉？ ? 沒錯！ 我們可以只看一邊 ? 繼續搜尋！ low 3 6 8 9 101 4 low high
- 27. 虛擬碼 - 解說 ? 當搜尋到 ? low >= high 或是 ? a[mid] = 想找的數字 ? 就大功告成了！ 1 3 4 6 8 9 10 highlow
- 28. 虛擬碼 - 整合 ? while (low < high) mid = (low + high) / 2 if (a[mid] == n) return mid else if (a[mid] < n) low = mid + 1 else if (a[mid] > n) high = mid – 1 return a[low] == n ? low : -1 當 low < high 就繼續搜尋 low high 1 3 4 6 8 9 101 3 4 6 8 9 10
- 29. 虛擬碼 - 整合 ? while (low < high) mid = (low + high) / 2 if (a[mid] == n) return mid else if (a[mid] < n) low = mid + 1 else if (a[mid] > n) high = mid – 1 return a[low] == n ? low : -1 1 3 4 6 8 9 103 4 6 8 9 10 low highmid 計算 mid (中點)
- 30. 虛擬碼 - 整合 ? while (low < high) mid = (low + high) / 2 if (a[mid] == n) return mid else if (a[mid] < n) low = mid + 1 else if (a[mid] > n) high = mid – 1 return a[low] == n ? low : -1 如果 mid 上的數字就是目標， 傳回結果 low highmid 1 3 4 6 8 9 103 4 6 8 9 10
- 31. 虛擬碼 - 整合 ? while (low < high) mid = (low + high) / 2 if (a[mid] == n) return mid else if (a[mid] < n) low = mid + 1 else if (a[mid] > n) high = mid – 1 return a[low] == n ? low : -1 如果目標應該在 右邊 就繼續在 右邊 搜尋 low highmid 1 3 4 6 8 9 103 4 6 8 9 10
- 32. 虛擬碼 - 整合 ? while (low < high) mid = (low + high) / 2 if (a[mid] == n) return mid else if (a[mid] < n) low = mid + 1 else if (a[mid] > n) high = mid – 1 return a[low] == n ? low : -1 如果目標應該在 右邊 就繼續在 右邊 搜尋 high 1 3 4 8 9 103 4 6 8 9 10 low
- 33. 1 3 4 6 8 9 10 虛擬碼 - 整合 ? while (low < high) mid = (low + high) / 2 if (a[mid] == n) return mid else if (a[mid] < n) low = mid + 1 else if (a[mid] > n) high = mid – 1 return a[low] == n ? low : -1 如果目標應該在 左邊 就繼續在 左邊 搜尋 low highmid
- 34. 3 6 8 9 101 4 虛擬碼 - 整合 ? while (low < high) mid = (low + high) / 2 if (a[mid] == n) return mid else if (a[mid] < n) low = mid + 1 else if (a[mid] > n) high = mid – 1 return a[low] == n ? low : -1 如果目標應該在 左邊 就繼續在 左邊 搜尋 low high
- 35. 3 6 8 9 101 4 虛擬碼 - 整合 ? while (low < high) mid = (low + high) / 2 if (a[mid] == n) return mid else if (a[mid] < n) low = mid + 1 else if (a[mid] > n) high = mid – 1 return a[low] == n ? low : -1 繼續從新的範圍搜尋 low high
- 36. 3 6 8 9 101 4 虛擬碼 - 整合 ? while (low < high) mid = (low + high) / 2 if (a[mid] == n) return mid else if (a[mid] < n) low = mid + 1 else if (a[mid] > n) high = mid – 1 return a[low] == n ? low : -1 ? 這樣應該能理解了吧 =D ？ 繼續從新的範圍搜尋 low high
- 37. Q&A 時間 ? 請問下面哪些數列可以做二分搜尋呢？ A) 1, 2, 3, 4, 5, 6, 7 B) 1, 3, 5, 7, 3, 5, 1 C) 4, 3, 2, 9, 8, 12 E) 1, 3, 4, 4, 6, 7, 7 D) 6, 5, 4, 3, 2, 1, -1 F) 2, 2, 2, 2, 2, 2, 2 ? 答案: A D E F
- 38. Q&A 時間 ? 請問下面哪些數列可以做二分搜尋呢？ A) 1, 2, 3, 4, 5, 6, 7 B) 1, 3, 5, 7, 3, 5, 1 C) 4, 3, 2, 9, 8, 12 E) 1, 3, 4, 4, 6, 7, 7 D) 6, 5, 4, 3, 2, 1, -1 F) 2, 2, 2, 2, 2, 2, 2 ? 答案: A D E F 你都答對了嗎？ A D E F
- 40. Q&A時間 - 接續 數列 整數 實數 可比較 遞增 遞減 單調 只要是一個可以互相 比較 的 單調 數列，即可使用二分搜尋 eg. 1.123, 2, 3.456, 3.456, 5.0, 8, 100, 2016.0325
- 41. Q&A時間 - 接續 數列 整數 實數 可比較 遞增 遞減 單調 只要是一個可以互相 比較 的 單調 數列，即可使用二分搜尋 eg. 1.123, 2, 3.456, 3.456, 5.0, 8, 100, 2016.0325 真的只有這樣嗎？
- 44. 想一想 - 1 ? 二分搜尋常被說是 ? 最容易寫錯 的演算法之一 ? 為什麼？
- 45. 想一想 - 2 ? 原問題：找一個數字 = n
- 46. 想一想 - 2 ? 原問題：找一個數字 = n ? 新問題：找第一個 >= n 的數字 ? 新問題：找第一個 > n 的數字 ? 要怎麼做呢？
- 49. 三分搜尋介紹 ? 我們來介紹二分搜尋的姊妹（？）－三分搜尋！ ? 簡單來說 三分搜尋 就是 找出極值點
- 50. 三分搜尋原理 ? 同樣利用單調性
- 52. 三分搜尋原理 ? 同樣利用單調性 1 個下降坡 1 個上升坡
- 53. 三分搜尋原理 ? 如果我在圖上任選 2 個點 ? 而 左點 比較 高
- 54. 三分搜尋原理 ? 如果我在圖上任選 2 個點 ? 而 左點 比較 高
- 55. 三分搜尋原理 ? 如果我在圖上任選 2 個點 ? 而 左點 比較 高
- 56. 三分搜尋原理 ? 如果我在圖上任選 2 個點 ? 而 左點 比較 高
- 57. 三分搜尋原理 ? 不論怎麼選
- 58. 三分搜尋原理 ? 不論怎麼選 ? 極值 都會在 左點 的 右手邊
- 59. 三分搜尋原理 ? 不論怎麼選 ? 極值 都會在 左點 的 右手邊 ? 因為只有 1 個下降坡，所以 左點 一定會在 下降坡 上
- 60. 三分搜尋原理 ? 同樣地，如果我選 2 個點，右點 比較 高
- 61. 三分搜尋原理 ? 同樣地，如果我選 2 個點，右點 比較 高
- 62. 三分搜尋原理 ? 同樣地，如果我選 2 個點，右點 比較 高 ? 極值 都會在 右點 的 左手邊 ? 因為只有 1 個上升坡，所以 右點 一定會在 上升坡 上
- 63. 三分搜尋原理 - 合併 ? 統整起來 ? 如果我選了 2 個點
- 64. 三分搜尋原理 - 合併 ? 統整起來 ? 如果我選了 2 個點 ? 1. 左點 比較 高 ? 極值 都會在 左點 的 右手邊
- 65. 三分搜尋原理 - 合併 ? 統整起來 ? 如果我選了 2 個點 ? 1. 左點 比較 高 ? 極值 都會在 左點 的 右手邊 ? 2. 右點 比較 高 ? 極值 都會在 右點 的 左手邊
- 66. 三分搜尋原理 - 合併 ? 統整起來 ? 如果我選了 2 個點 ? 1. 左點 比較 高 ? 極值 都會在 左點 的 右手邊 ? 2. 右點 比較 高 ? 極值 都會在 右點 的 左手邊 ? 所以，雖然比較複雜 我還是可以藉由 選 2 個點 縮小 搜尋範圍
- 67. 三分搜尋流程 ? 左點 比較 高 ? 極值 在 右手邊
- 68. 三分搜尋流程 ? 縮小 搜尋範圍
- 69. 三分搜尋流程 ? 右點 比較 高 ? 極值 在 左手邊
- 70. 三分搜尋流程 ? 可以預見 ? 範圍會持續 縮小 ? 直到找到 極值
- 71. 三分搜尋流程 ? 可以預見 ? 範圍會持續 縮小 ? 直到找到 極值 在這裡！
- 72. 三分搜尋流程 ? 可以預見 ? 範圍會持續 縮小 ? 直到找到 極值 在這裡！ 這，就是 三分搜尋
- 73. 想一想 - 3 ? 要怎麼選這 2 個點呢？
- 74. 想一想 - 3 ? 要怎麼選這 2 個點呢？ ? 選 1/3 跟 2/3？
- 75. 想一想 - 3 ? 要怎麼選這 2 個點呢？ ? 選 1/3 跟 2/3？ ? 這樣選真的比較好嗎？
- 76. 想一想 - 4 ? 三分搜尋可不可以 ? 一字不改 取代 二分搜尋？
- 77. 想一想 - 4 ? 三分搜尋可不可以 ? 一字不改 取代 二分搜尋？ ? 為什麼？