7.13 二分法

二分法模板

• 给定已排序的数组, 和target, 查找数组中任意一个/第一个/最后一个位置的target, 如果找不到则返回-1

二分位置(Binary Search on Index)

• 找到满足某个条件的第一个位置或者最后一个位置

• 保留有解的一半, 或者去掉无解的一半

• 根据时间复杂度倒推算法是面试中的常用策略

  • O(1)很少遇到
  • O(logn)几乎是二分法
  • O(✓n)几乎是分解质因数
  • O(n)高频
  • O(nlogn)一般可能要排序
  • O(n^2)数组, 枚举, 动态规划
  • O(n^3)数组, 枚举, 动态规划
  • O(2^n)与组合有关的搜索
  • O(n!)与排列有关的搜索

二分法

• 初级之二分法模板

#	Title	Solution	Difficulty	Source Code	From
14	First Position of Target		Easy	FirstPositionofTarget.java	lintcode
xx	Last Position of Target		Easy	LastPositionofTarget.java	github

• 进阶之二分位置(已知数组, 查找数组第一个/最后一个满足条件的位置)

  • 未知长度的排序数组, 查找target使用倍增(double)思路, 找到k-2k的范围, 再二分查找; 例题: search-in-a-sorted-array-of-unknown-size或者Search in a Big Sorted Array | # | Title | Solution | Difficulty | Source Code | From | | —- | —– | ——– | ———- | ———– | ———– | | 74 | First Bad Version | | Medium | FirstBadVersion.java | lintcode | | 702 | search-in-a-sorted-array-of-unknown-size | double | Medium | SearchInaSortedArrayOfUnknownSize.java | leetcode |

  • Rotate Array

  #	Title	Solution	Difficulty	Source Code	From
  6	Rotate String		Easy	RotateString.java	lintcode
  39	Recover Rotated Sorted Array		Easy	RecoverRotatedSortedArray.java	lintcode
  159	Find Minimum in Rotated Sorted Array		Medium	FindMinimuminRotatedSortedArray.java	lintcode

  • Search a 2D Matrix

  #	Title	Solution	Difficulty	Source Code	From
  28	Search a 2D Matrix		Easy	Searcha2DMatrix.java	lintcode
  38	Search a 2D Matrix II		Medium	Searcha2DMatrixII.java	lintcode

  • Search for a Range

  #	Title	Solution	Difficulty	Source Code	From
  61	Search for a Range		Medium	SearchforaRange.java	lintcode

  #	Title	Solution	Difficulty	Source Code	From
  585	Maximum Number in Mountain Sequence		Medium	MaximumNumberinMountainSequence.java	lintcode
  600	Smallest Rectangle Enclosing Black Pixels		Hard	SmallestRectangleEnclosingBlackPixels.java	lintcode

• 高阶之二分位置 Half half(去掉一半留下一半, 二分本质)
  • 并无法找到条件形成OOXX的模型, 但可以根据判断, 保留下有解的那一半或者去掉无解的一半
  • 目标是达到时间复杂度为O(logn)

  #	Title	Solution	Difficulty	Source Code	From
  75	Find Peak Element		Medium	FindPeakElement.java	lintcode
  62	Search in Rotated Sorted Array		Medium	SearchinRotatedSortedArray.java	lintcode

参考

• lintcode