Insights of Binary Search

1. The size of search space ([L, M] or {m, R]) is reduced roughly by one half of the previous iteration and eventually the search space is reduced to 2 elements and to 1 element eventually.
2. 我们不能狭义地认为，binary search就是找sorted array里的一个target
   1. 清楚target一定不在哪一部分
   2. 把问题model成search space的分界线问题

<aside> 💡 Principles of Binary Search

1. Search Space decreases over time
2. target can’t be ruled out. </aside>

举个栗子

二分查找的易错点：

Example：

given an array [1, 2, 3, 5, 5, 5, 8, 9]

1. find the first element ≥ 5
2. find the last element < 5
3. find the first element > 5
4. find the last element ≤ 5

可以看到仅仅是细节不同的问题，答案却截然不同，binary search的细节处理并不容易

一些做题整理

Untitled

1. while loop里的条件

   1. while (left < right)

      1. 出循环的条件是left == right，有一个元素；
      2. 不断缩小array的范围，直到最后一个值一定是要找的答案。
      3. 这类问题通常是找这个array里一定会有的元素，eg：peak，找minimum，missing number；

   2. while (left <= right)

      1. 看完array里所有元素才会出循环，如果没找到通常会return -1；
      2. 常出现在找target的题；

   3. while (left < right - 1)

      1. 至少需要三个元素才能进循环，出循环时有两个元素还没看；
      2. 通常需要post- processing，比较出循环时剩的两个元素；
      3. 这类问题通常是找first/ last occurrence 或者 closest elements；

2. mid 和谁做比较

   1. array[mid] < array[mid + 1]

      1. 通常根据array的性质单调递增或者单调递减来做判断，题目通常在此性质上做文章，比如找peak / local minimum
      2. array[mid] < array[mid + 1] increasing
      3. array[mid] < array[mid - 1] decreasing

   2. array[mid] > array[left]/ array[mid] < array[right]

      1. 常出现在rotated array，这样的array有性质，即array[right] < array[left](if contains duplicates array[right] <= array[left])

   3. array[mid] > target

      1. 根据中点与target做比较，舍掉target不在的一半。

3. 如何移动left / right，通常需要判断mid包不包含target

   1. left = mid + 1;
   2. right = mid - 1;
   3. left = mid; right = mid;