【一】'二分'算法原理剖析
二分查找通常要求数据有序。其本质是通过目标值排除一半的区间,解决传统的从头到尾遍历查找。只要目标数据与目标值满足一定的大小关系,即可使用二分法。
第一套模版:
int left = 0, right = nums.size() - 1;
int mid = 0; //找左端点
while (left < right) {
mid = (right + left) / 2;
if (nums[mid] > target) right = mid - 1;
else if (nums[mid] < target) left = mid + 1;
}
第二套模板: 推论:假设找 target 连续的区间(找左端点)
首先看左边区间:如果 mid 落在左边的区间,那么 mid 不可能命中到目标值,left = mid + 1。 8 在右边的一坨中,那么 mid 不能超过这个区间(竖划线),right = mid。 mid 的中值计算应该为:left + (right - left) / 2(计算左端点)。 循环条件应该是:left < right,如果等于,会由于判断条件导致循环。 现象:如果 mid 落在左边,就必须超过竖划线收缩;在右边应该不断收缩,但是不能超过竖划线。
int left = 0, right = nums.size() - 1;
int mid = 0; //找左端点
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] >= target) right = mid;
else if (nums[mid] < target) left = mid + 1;
}
第三套模板: 推论:假设找 target 连续的区间(找右端点)
首先看左边区间:如果 mid 落在左边的区间,那么 mid 可能命中到目标值,left = mid。 mid 落在右边的一坨,那么 mid 不能超过这个区间,right = mid - 1。 mid 的中值计算应该为:left + (right - left + 1) / 2(计算右端点)。 循环条件应该是:left < right,如果等于,会由于判断条件导致循环。 现象:如果 mid 落在左边,就不能超过竖划线收缩;在右边应该不断收缩,必须要超过竖划线。
//找右端点
left = 0, right = nums.size() - 1;
while (left < right) {
mid = left + (right - left + ) / ;
(nums[mid] > target) right = mid - ;
(nums[mid] <= target) left = mid;
}


