Binary search and Divide and Conquer

Binary search 非常 tricky，虽说道理简单，但是面试的时候却很容易出 bug，因此总结一下是必须的。

终止条件不同

i <= j
i < j

mid 的上下取向不同

i + (j - i) / 2
j - (j - i) / 2

如何合理分半

分半的时候取 mid, mid-1, or mid+1

举例

  • lc74: Search a 2D Matrix： 这是一道普通的binary search。终止条件i <= j, mid 取向 i + (j - i) / 2, 分半的时候 = mid - 1 or mid + 1。

  • lc34: Search for a Range：这道题需要终止条件i < j, mid 取向两种都需要用到，分半的时候需要用到 = mid。我发现一般＝mid的时候，终止条件往往是i < j,不然会有死循环。

  • 合理分半：下边这几道题都很tricky，分半的时候都有各自的特点，很不容易一次 写对。需要多多练习和体会。

lc33: Search in Rotated Sorted Array

lc81: Search in Rotated Sorted Array II

lc4: Median of Two Sorted Arrays

其他一些不容易看出来是 binary search 的题目

  • lc29: Divide Two Integers：这题没做过面试也容易跪

  • lc50: Pow(x, n)

  • lc69: Sqrt(x)：其实算是一道典型的binary search题目，不过里边包括了几个tricky 的地方，很难一次写对

PreviousBasic Data StructuresNextBinary Tree

Last updated