算法完全搞懂二分查找（包括左边界、右边界查找）

桃扇骨 2022-11-21 15:18 123阅读 0赞

> 博主习惯左闭右闭的搜索区间，所以以下三种二分查找方法都是以 `[left, right]` 作为搜索区间

### 一、基本版 ###

1.  `target` 在数组中重复存在时，不考虑按边界输出，只要找到，立刻输出其下标
2.  实现
    
        function binarySearch(_arr, _target){ 
          /** * 二分搜索基本版：找到立即输出下标，不考虑需要找左边界还是右边界 * 搜索区间，左闭右闭 * @param {Array} _arr: 升序数组 * @param {Number} _target: 目标值 */
          let left = 0, right = _arr.length - 1;
          while(left <= right){  // 左闭右闭，left===right时有一个元素
            let mid = left + Math.floor((right - left) / 2);  // (right - left) 有效防止 left + right 越界
            if(_target < _arr[mid]){ 
              right = mid - 1;
            }
            else if(_target > _arr[mid]){ 
              left = mid + 1;
            }
            else{ 
              return mid;
            }
          }
          return -1;
        }

### 二、左边界版 ###

1.  `target` 在数组中重复存在时，输出最左侧元素的下标
2.  实现
    
        function left_bound(_arr, _target){ 
          /** * 二分搜索左边界版：当有多个符合_target时，输出最左侧元素的索引 * 搜索区间，左闭右闭 * @param {Array} _arr: 升序数组 * @param {Number} _target: 目标值 */
          let left = 0, right = _arr.length - 1;
          while(left <= right){ 
            let mid = left + Math.floor((right - left) / 2);
            if(_target < _arr[mid]){ 
              right = mid - 1;
            }
            else if(_target > _arr[mid]){ 
              left = mid + 1;
            }
            else{ 
              right = mid - 1;  // 重点，找到_target时，不返回，而是进一步缩小搜索区域
                                // 可以想想最终right的含义是什么（ans: 数组中比_target小的最大元素的下标）
            }
          }
          // 循环退出条件：left = right + 1，结合right含义，left就是我们要找的索引
          // 找不到_target的两种情况，left越界，或找不到比_target小的元素，此时right为-1，left为0但_arr[left] !== _target
          if(left >= _arr.length || _arr[left] !== _target) return -1;
          return left; 
        }

### 三、右边界版 ###

1.  `target` 在数组中重复存在时，输出最右侧元素的下标
2.  实现
    
        function right_bound(_arr, _target){ 
          /** * 二分搜索左边界版：当有多个符合_target时，输出最右侧元素的索引 * 搜索区间，左闭右闭 * @param {Array} _arr: 升序数组 * @param {Number} _target: 目标值 */
          let left = 0, right = _arr.length-1;
          while(left <= right){ 
            let mid = left + Math.floor((right - left)/2);
            if(_target < _arr[mid]){ 
              right = mid - 1;
            }
            else if(_target > _arr[mid]){ 
              left = mid + 1;
            }
            else{ 
              left = mid + 1;  // 重点，找到_target时，不返回，而是进一步缩小搜索区域
                               // 可以想想最终left的含义是什么（ans: 数组中比_target大的最小元素的下标）
            }
          }
          // 循环退出条件 left = right + 1，结合left含义，right就是我们要找的元素的索引
          // 找不到的两种情况：left为0时，right为-1；left越界了，仍找不到满足的元素，此时right为数组最后一个元素
          if(right < 0 || _arr[right] !== _target) return -1;
          return right; 
        }

> [参考][Link 1]

[Link 1]: https://mp.weixin.qq.com/s/M1KfTfNlu4OCK8i9PSAmug