Binary Search
- 2 minutes read - 365 wordsServeral months ago, I practiced serveral binary leetcode questions, and I was confused about the following several things: I didn’t pay much attentions to it then, I thought I will get the hang of it after serveral practices. However after serveral practice, I still confused in binary search problems. Latest week an article mentions binary search at https://leetcode.wang/. Little searching, I found more information about this such as lower bound, upper bound, equal-range, open/close range, middle point etc. There are more choices than a normal lecture ppt.
-
< vs ⇐
-
mid minus/plus 1
-
why without minus/plus 1
-
loop invariant
-
[first, last) range: mid = first + (last -first)/2; make sure when there is only one element in the range, mid = first.
-
(first, last] : mid = last - ( last-first)/2; make sure when there is only one element in the range, mid = last.
-
while loop的循环不变量 - loop invariants（怎样缩小区间才不出错）（会写代码 vs 会用计算机科学的思考方式)
-
Confuse in Binary Search when to use left < right ; left ⇐ right ; and few more
binary_search(lo, hi, p):
while lo < hi:
mid = lo + (hi - lo) / 2
if p(mid) == true:
hi = mid
else :
lo = mid + 1
if p(lo) == false:
complain // p(x) is false for all x in S!
return lo // lo is the least x for which p(x) is true
The two crucial lines are hi = mid and lo = mid+1. When p(mid) is true, we can discard the second half of the search space, since the predicate is true for all elements in it (by the main theorem). However, we can not discard mid itself, since it may well be the first element for which p is true. This is why moving the upper bound to mid is as aggressive as we can do without introducing bugs. In a similar vein, if p(mid) is false, we can discard the first half of the search space, but this time including mid. p(mid) is false so we don’t need it in our search space. This effectively means we can move the lower bound to mid+1.