其实,二分查找看起来so easy,但它的各种变形扣边界真的需要总结一下。
注意:以下代码均采用左右均为闭区间,即hi为最后一个元素下标,而不是元素个数。
base case
无重复数字,找target的下标
1 | /** |
1 | // 递归版 |
查找>=target的最小下标
1 | /** |
查找<=target的最大下标
1 | /** |
base case上的改进
查找>target的最小下标
1 | /** |
查找<target的最大下标
1 | /** |
查找target的最小下标
1 | /** |
不基于前面的直接写:
1 | public static int findLeftIndex2(int[] nums, int target) { |
查找target的最大下标
1 | /** |
不基于前面的直接写:
1 | public static int findRightIndex2(int[] nums, int target) { |
查找target出现的次数
1 | /** |
有序数组断成两节互换位置后查找最小值的下标
1 | /** |
汇总和测试函数
1 | package array; |