二分搜尋利用已排序資料的特性，每次將搜尋範圍縮小一半，時間複雜度從 O(n) 降到 O(log n)。

Notes:

  • 不只適用於排序陣列，任何具有「單調性」的搜尋空間都可以用二分搜尋
  • 注意邊界條件：left、right 的初始值，以及 mid 的計算方式
  • 常見變體：找左邊界、找右邊界、在答案空間上二分

跨倉庫導讀#

#4 Median of Two Sorted Arrays #33 Search in Rotated Sorted Array #34 Find First And Last Position of Element In Sorted Array #35 Search Insert Position #69 Sqrt(x) #74 Search a 2D Matrix #81 Search In Rotated Sorted Array II #116 Populating Next Right Pointers In Each Node #153 Find Minimum in Rotated Sorted Array #162 Find Peak Element #367 Valid Perfect Square #374 Guess Number Higher Or Lower #410 Split Array Largest Sum #441 Arranging Coins #540 Single Element in a Sorted Array #704 Binary Search #875 Koko Eating Bananas #977 Squares of a Sorted Array #981 Time Based Key-Value Store #1011 Capacity to Ship Packages #1268 Search Suggestions System #1898 Maximum Number of Removable Characters #2300 Successful Pairs of Spells and Potions #2616 Minimize the Maximum Difference of Pairs
Backward 2390. Removing Stars From a String 4. Median of Two Sorted Arrays Forward