Binary Search

思考方法

1. 想想這個題目的 search space 是什麼，知道怎麼定義 start, end

2. 想想如果算出 mid，該怎麼一次排除一半的 search space

3. 想想如果 mid == target，該怎麼處理

4. 有沒有額外的 case 要在二分搜尋的 while loop 外處理

題型分類

1. 基本 binary search 熟悉

   • 704 - Binary Search

2. 需要修改找到 target 時的處理方法或額外處理別的 case，而不只是 return 找到了

   • 34 - Find First and Last Position of Element in Sorted Array

   • 35 - Search Insert Position

3. 對部分有序的 array 進行搜尋

   • 33 - Search in Rotated Sorted Array

   • 81 - Search in Rotated Sorted Array II

   • 153 - Find Minimum in Rotated Sorted Array

4. 非直接有序 or 部分有序，但可以用特別的條件二分搜尋

   • 162 - Find Peak Element

5. Search space 從 array 變成數字範圍

   • 50 - Pow(x, n): Search space 介於 $x$ 到 $x^n$
   • 69 - Sqrt(x): Search space 介於 $0$ 到 $x$
   • 29 - Divide Two Integers: Search space 介於 $1$ 到 $dividend$
6. Search space 變成 2D array

   • 240 - Search a 2D Matrix II