二分法题型一
二分位置 之 OOXX,一般会给你一个数组,让你找数组中第一个/最后一个满足某个条件的位置:OOOOOOO…OOXX….XXXXXX。
- Leetcode - 278 First Bad Version
- Lintcode - 159 Find Minimum in Rotated Sorted Array
- Leetcode - 74 Search a 2D Matrix
- Lintcode - 61 Search for a Range
模板
1 | public int findPosition(int[] nums, int target) { |
二分法题型二
第二境界 二分位置 之 Half half,并无法找到一个条件,形成 OOXX 的模型,但可以根据判断,保留下有解的那一半或者去掉无解的一半
- Lintcode - 75 Find Peak Element
- Lintcode - 585 Maximum Number in Mountain Sequence
二分答案 Binary Search on Result
往往没有给你一个数组让你二分 而且题目压根看不出来是个二分法可以做的题
同样是找到满足某个条件的最大或者最小值