二分查找算法原理及常见变种解析

一、'二分'算法原理剖析

'二分'的刻板印象是目标数据需要有序，如 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;
}