二分查找 - 二分查找模板 - 《数据结构和算法》

基础模板

基础模板

function binarySearch(nums, target) {
    let left = 0, right = ...;
    while(...) {
        let mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

注意：

不要出现 else
计算 mid 时需要防止溢出,代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出

一、寻找一个数（基本的二分搜索
此算法是左闭右闭
【 left，right 】

function binarySearch( nums, target) {
    let left = 0; 
    let right = nums.length - 1; // 注意
    while(left <= right) {
        let mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

二、寻找左侧边界的二分搜索

此算法是左闭右开
【 left，right ）

function left_bound(nums, target) {
  if (nums.length == 0) return -1;
  let left = 0;
  let right = nums.length; // 注意
  while (left < right) { // 注意
      let mid = (left + right) / 2;
      if (nums[mid] == target) {
          right = mid;
      } else if (nums[mid] < target) {
          left = mid + 1;
      } else if (nums[mid] > target) {
          right = mid; // 注意
      }
  }
  if (left == nums.length || nums[left] !== target ) {
    return -1;
  }
  return left;
}

最后不符合left < right

边界问题的讨论

如果target 是0 ，不在区间范围内，如图所示

那么在寻找的过程中，right就会一直往左缩减，最后成为如下所示的样子

此时，不符合left<right,遍历结束,触发边界

 nums[left] !== target

如果是一个极大值呢？

在第一轮循环之后演变成如下图所示

此时再次循环的话left 会落在如下位置

超出范围触发边界

left == nums.length

极大极小的情况有了，那如果是在区间内，没有找到值呢

最终都会触发

 nums[left] !== target

统一一下都变成左闭右闭

function left_bound(nums,  target) {
    let left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        let mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.length || nums[left] != target){
        return -1;
    }
    return left;
}

三、寻找右侧边界的二分搜索

此算法是左闭右开
【 left，right ）

function right_bound( nums, target) {
    if (nums.length == 0) return -1;
    let left = 0, right = nums.length;

    while (left < right) {
        let mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
  if (left == 0 || nums[right] != target) {
    return -1
  };
    return left - 1; // 注意
}

四、三者统一的二分算法模板

将「搜索区间」全都统一成两端都闭，好记，只要稍改 nums[mid] == target 条件处的代码和返回的逻辑即可

// 搜索一个数
function binary_search(nums, target) {
    let left = 0, right = nums.length - 1; 
    while(left <= right) {
        let mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 搜索一个数直接返回
            // 搜索左侧边界，右值减小
            // 搜索右侧边界，左值减小
            ...
            ...
            ...
        }
    }
    // 处理左右侧边界越界问题
      ... 
      ... 
      ...
    // 返回
    return ...;
}

// 搜索一个数
function binary_search(nums, target) {
    let left = 0, right = nums.length - 1; 
    while(left <= right) {
        let mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

// 寻找左侧边界的二分搜索
function left_bound(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        let mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

// 寻找右侧边界的二分搜索
function right_bound(nums,  target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        let mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

总结

建议使用统一二分模板，不去考虑左闭右开或者左右闭合的边界问题

选用左右都闭合，left = 0,right = arr.length-1
在left < right 的循环范围内去寻找目标值
找目标
1. 如果是寻找目标，当 nums[mid] = target 时候就返回
2. 如果是寻找左边界，当 nums[mid] = target 时候就向左查找
  1. 当不满足循环的时候处理边界，返回left
  2. 边界是left >= nums.length || nums[left]!==target
3. 如果是寻找右边界，当 nums[mid] = target 时候就向右查找
  1. 当不满足循环的时候处理边界，返回right
  2. 边界是right <0 || nums[right]!==target

二分查找模板