一、'二分'算法原理剖析
'二分'的刻板印象是目标数据需要有序,如 0,1,2,3,4,5。但'二分'的本质是通过目标值排除一半区间,解决传统的从头到尾遍历查找。只要目标数据与目标值满足一定的大小关系,即可应用。
第一套模版:
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;
}


