Skip to content

Binary Search Template

Binary search, 本身的思路并不难，难就难在

  • should we use while left <= right or while left < right?
  • should we update left pointers as left = mid or left = mid + 1?
  • do we return left or left - 1

binary search可以有多种写法，如果每次都写的不一样，就会造成对于结束条件，指针变化的混乱，所以我们要找到一种固定的模板，通过修改模板来解决题目.

Templates

有很多大神的经验，总结出来了很多模版。这里我们根据一些经典binary search题目作为metrics, 来评价一下这个模版的general性.

Template 1: Comment from LC

这个template是704 binary search的editorial下面回复区提供的模版.

def search(self, nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] >= target:
            hi = mid
        else:
            lo = mid + 1

    if nums[lo] == target:
        return lo
    else:
        return -1

Reference