Open caipengbo opened 5 years ago
思想:有序(数组有序、范围的潜在有序)、找边界(临界点)、(尝) 试每次取到的mid(g函数的设计)
区间左闭右 [start, end )
开模板
int start = 0, end = length - 1;
while(start < end) {
mid = start + (end - start) / 2;
if g(mid)
end = mid ; // 左侧
else
start = mid + 1; // 右侧
}
return start; // or how to use upper bound (start)
- 首先明确我们是对索引进行二分还是对值进行二分(有时忘记是索引,导致马虎出现bug)
- 注意初始位置(
start
和end
),end = length-1
和end = length
结果是一样的(???n=2的时候剑指offer P3.2题),用作数组下标的时候最好使用end = length-1
g( )
函数:最终返回的是,第一个满足g(m) == true
的元素下标m
(注意end = mid
在前面时)- 返回
start
, 找不到时,会返回左边界或者右边界(上图说的不太对)
(数组的) 索引搜索 和 (范围的) 值搜索
找不到的情况?越界问题? 例 (一个非常好的题目) 寻找有序数组中,比val值小的数的个数,注意val不一定在数组中,并且数组中可能含有重复元素
public int findKSmallest(int[] nums, int val) {
if (nums.length == 0) return 0;
int l = 0, r = nums.length-1, m;
while (l < r) {
m = l + (r - l) / 2;
if(nums[m] > val) r = m;
else l = m + 1;
}
if (nums[l] > val) return l; // 如何利用边界
return l+1;
}
堆和二分查找方法
**这一点需要对比一下
行列都排序的二维数组的 Kth 问题
LeetCode:378, 668, 719, 786
如何转换成 二维问题?? 设置两个方向的坐标i j 然后映射到 input的一维数组上
这里,g函数有一个统计的过程,通过count与K进行比较,来缩短区间
例题 240题
1) everytime check if targe == nums[mid], if so, we find it.
2) otherwise, we check if the first half is in order (i.e. nums[left]<=nums[mid])
and if so, go to step 3), otherwise, the second half is in order, go to step 4)
3) check if target in the range of [left, mid-1] (i.e. nums[left]<=target < nums[mid]), if so, do search in the first half, i.e. right = mid-1; otherwise, search in the second half left = mid+1;
4) check if target in the range of [mid+1, right] (i.e. nums[mid]<target <= nums[right]), if so, do search in the second half, i.e. left = mid+1; otherwise search in the first half right = mid-1;
The only difference is that due to the existence of duplicates, we can have nums[left] == nums[mid] and in that case, the first half could be out of order (i.e. NOT in the ascending order, e.g. [3 1 2 3 3 3 3]) and we have to deal this case separately. In that case, it is guaranteed that nums[right] also equals to nums[mid], so what we can do is to check if nums[mid]== nums[left] == nums[right] before the original logic, and if so, we can move left and right both towards the middle by 1. and repeat.
g函数 if (nums[mid] < nums[hi])
以前的相关题目记录: Weekly Contest : https://github.com/caipengbo/AlgoEx/issues/2 剑指offer: https://github.com/caipengbo/Coding-Interviews/issues/33