Insights of Binary Search
- 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.
- 我们不能狭义地认为,binary search就是找sorted array里的一个target
- 清楚target一定不在哪一部分
- 把问题model成search space的分界线问题
<aside> 💡 Principles of Binary Search
二分查找的易错点:
Example:
given an array [1, 2, 3, 5, 5, 5, 8, 9]
可以看到仅仅是细节不同的问题,答案却截然不同,binary search的细节处理并不容易
while loop里的条件
while (left < right)
left == right
,有一个元素;while (left <= right)
while (left < right - 1)
mid 和谁做比较
array[mid] < array[mid + 1]
array[mid] < array[mid + 1]
increasingarray[mid] < array[mid - 1]
decreasingarray[mid] > array[left]
/ array[mid] < array[right]
array[right] < array[left]
(if contains duplicates array[right] <= array[left]
)array[mid] > target
如何移动left / right,通常需要判断mid包不包含target
left = mid + 1
;right = mid - 1
;left = mid; right = mid
;