第 150 题：二分查找如何定位左边界和右边界

Question

不使用 JS 数组 API，查找有序数列最先出现的位置和最后出现的位置。

Answer 1

var search = function (nums, target, isBorder) {
  let min = 0;
  let max = nums.length - 1;
  let isRightBorder = false;
  let isLeftBorder = false;
  if (isBorder === "left") {
    isLeftBorder = true;
  } else if (isBorder === "right") {
    isRightBorder = true;
  }
  while (min <= max) {
    let mid = Math.ceil((max + min) / 2);
    let cur = nums[mid];
    if (cur === target) {
      if (isLeftBorder) {
        mid = mid - 1;
        if (nums[mid] !== target) {
          return mid + 1;
        }
        max = mid;
      } else if (isRightBorder) {
        mid = mid + 1;
        if (nums[mid] !== target) {
          return mid - 1;
        }
        min = mid;
      } else {
        return mid;
      }
    } else if (target > cur) {
      min = mid + 1;
    } else {
      max = mid - 1;
    }
  }
  return -1;
};

Answer 2

稍微对二分查找改造一下就可以，找到目标值之后左右滑动确定值

 function findBoundary(source, target, start = 0, end = source.length - 1) {
    if (end - start === 1) {
      if (source[start] !== target) return -1;
      return leftAndRight(source, target, start);
    }
    const mid = start + Math.floor((end - start) / 2);
    if (source[mid] < target) {
      return findBoundary(source, target, mid, end);
    } else if (source[mid] > target) {
      return findBoundary(source, target, start, mid);
    } else {
      return leftAndRight(source, target, mid);
    }
  }

  function leftAndRight(source, target, mid) {
    let i = mid;
    let j = mid;
    while (source[i - 1] === target) {
      i--;
    }
    while (source[j + 1] === target) {
      j++;
    }
    return [i, j];
  }

Answer 3

/**
 * 寻找目标值左侧边界
 * @param {*} nums 
 * @param {*} target 
 */
function findLeft(nums, target) {

    let left = 0;
    let right = nums.length;

    while (left < right) {

        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            right = mid; //关键地方
        } else if (nums[mid] > target) {
            right = mid; //关键地方
        } else {
            left = mid + 1;
        }
    }

    return left;
}

/**
 * 寻找目标值右侧边界
 * @param {*} nums 
 * @param {*} target 
 */
function findRight(nums, target) {

    let left = 0;
    let right = nums.length;

    while (left < right) {

        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            left = mid + 1 //关键地方
        } else if (nums[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;//关键地方
        }
    }

    return left;
}

let arr = [1, 3, 4, 4, 6, 8, 10];

console.log('left bound:', findLeft(arr, 4))

console.log('right bound:', findRight(arr, 4))

findRight 应当返回left - 1

function findLeft(nums: number[], target: number): number {
  let left = 0
  let right = nums.length

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] === target) {
      right = mid
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      right = mid
    }
  }

  if (nums[left] !== target) {
    return -1
  }

  return left
}

function findRight(nums: number[], target: number): number {
  let left = 0
  let right = nums.length

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] === target) {
      left = mid + 1
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      right = mid
    }
  }

  if (nums[left - 1] !== target) {
    return -1
  }

  return left - 1
}

Answer 4

/**
 * 寻找目标值左侧边界
 * @param {*} nums 
 * @param {*} target 
 */
function findLeft(nums, target) {

    let left = 0;
    let right = nums.length;

    while (left < right) {

        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            right = mid; //关键地方
        } else if (nums[mid] > target) {
            right = mid; //关键地方
        } else {
            left = mid + 1;
        }
    }

    return left;
}

/**
 * 寻找目标值右侧边界
 * @param {*} nums 
 * @param {*} target 
 */
function findRight(nums, target) {

    let left = 0;
    let right = nums.length;

    while (left < right) {

        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            left = mid + 1 //关键地方
        } else if (nums[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;//关键地方
        }
    }

    return left;
}

let arr = [1, 3, 4, 4, 6, 8, 10];

console.log('left bound:', findLeft(arr, 4))

console.log('right bound:', findRight(arr, 4))

findRight 应当返回left - 1

Answer 5

• 边界条件
  • 选用[leftIndex, rightIndex)左闭右开区间，区间的选择会影响终止条件的判断
• 中间值选择
  • 向前取整，假设当区间为[4, 5)时，midIndex = Math.floor((4 + 5) / 2) = 4，符合预期
• 终止条件
  • 当leftIndex == rightIndex时，区间[leftIndex, rightIndex)无法匹配任何值，终止循环/递归
• 最先出现的位置firstIndex
  • 二分查找找到第一个值后，重置区间为[leftIndex, midIndex)并记录firstIndex，重复直到达到终止条件
• 最后出现的位置lastIndex
  • 二分查找找到第一个值后，重置区间为[midIndex + 1, rightIndex)并记录lastIndex，重复直到达到终止条件

// 非递归解法, 查lastIndex原理一样
function searchFirstIndex(arr, target) {
	let firstIndex = -1
	let leftIndex = 0
	let rightIndex = arr.length  // 初始区间为[0, arr.length)
	// leftIndex == rightIndex时终止循环
	while(leftIndex < rightIndex) {
		let midIndex = Math.floor((leftIndex + rightIndex) / 2)
		let mid = arr[midIndex]
		if(mid == target) {
			if(firstIndex == -1 || firstIndex > midIndex) {
				firstIndex = midIndex
				rightIndex = midIndex	// 继续向左查找
			}
		} else if(mid < target) {
			leftIndex = midIndex + 1
		} else if(mid > target) {
			rightIndex = midIndex
		}
	}
	return firstIndex
}

Answer 6

递归实现

/**
 * @param {Array} arr 数组
 * @param {Number} item 待查找项
 * @param {Number} min 第一个索引
 * @param {Number} max 最后一个索引
 */
function _binarySearch(arr, item, min = 0, max = arr.length - 1) {
  const half = Math.floor(min + (max - min) / 2)
  if (item < arr[half]) return _binarySearch(arr, item, min, half - 1)
  if (item > arr[half]) return _binarySearch(arr, item, half + 1, max)
  return half
}
/**
 * @param {Array} arr 数组
 * @param {Number} item 待查找项
 */
const binarySearch = (arr, item) => _binarySearch(arr, item) // 隐藏多余参数

循环实现：

/**
 * @param {Array} arr 数组
 * @param {Number} item 待查找项
 */
function binarySearch(arr, item) {
  let min = 0
  let max = arr.length - 1
  let half
  while (min <= max) {
    half = Math.floor(min + (max - min) / 2)
    if (item > arr[half]) {
      min = half + 1
    } else if (item < arr[half]) {
      max = half - 1
    } else {
      break
    }
  }
  return half
}

测试：

/**
 * test
 */
const res = binarySearch([1, 3, 66, 88, 233, 666], 666)
console.log('res: ', res) // 5

Answer 7

let arr = [0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9];
    const binarySearch = (arr,target) => {
        // 查找左边界
        const handleSearchL = (i, j) => {
            // 中位数偏左
            const mid = Math.floor((i+j)/2);
            // 如果i找到且i与j相等
            if (i === j && arr[i] === target) {
                return i;
            } else if( i === j) {
                // 没找到目标
                return -1;
            }
            // 中位数的值与目标相等向左缩小范围
            if (arr[mid] === target) {
                return handleSearchL(i, mid);
            }
            // 中位数的值比目标小说明范围在右侧，且中位数的值已排除所以mid+1
            if (arr[mid] < target) {
                return handleSearchL(mid + 1, j);
            }
            // 中位数的值比目标大说明范围在左侧，且中位数的值已排除所以mid-1
            if (arr[mid] > target) {
                return handleSearchL(i, mid - 1);
            }
        }
        const handleSearchR = (i, j) => {
            const mid = Math.ceil((i + j)/2);
            if (i === j && arr[i] === target) {
                return i;
            } else if( i === j) {
                return -1;
            }
            if (arr[mid] === target) {
                return handleSearchR(mid, j);
            }
            if (arr[mid] < target) {
                return handleSearchR(mid + 1, j);
            }
            if (arr[mid] > target) {
                return handleSearchR(i, mid - 1);
            }
        }
        // 找到左侧的值
        const left = handleSearchL(0, arr.length - 1);
        // 未找到说明没有该值存在
        if (left === -1) return [-1, -1];
        // 已知左侧范围找右侧的边界
        const right = handleSearchR(left, arr.length - 1);
        return [left, right];
    }
    console.log(binarySearch(arr,5));  // [11,13]

Answer 8

/**
 * 寻找目标值左侧边界
 * @param {*} nums 
 * @param {*} target 
 */
function findLeft(nums, target) {

    let left = 0;
    let right = nums.length;

    while (left < right) {

        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            right = mid; //关键地方
        } else if (nums[mid] > target) {
            right = mid; //关键地方
        } else {
            left = mid + 1;
        }
    }

    return left;
}

/**
 * 寻找目标值右侧边界
 * @param {*} nums 
 * @param {*} target 
 */
function findRight(nums, target) {

    let left = 0;
    let right = nums.length;

    while (left < right) {

        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            left = mid + 1 //关键地方
        } else if (nums[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;//关键地方
        }
    }

    return left;
}

let arr = [1, 3, 4, 4, 6, 8, 10];

console.log('left bound:', findLeft(arr, 4))

console.log('right bound:', findRight(arr, 4))

Answer 9

题目介绍

二分查找定位左边界和右边界

knuth 说过，二分查找虽然思路很简单，但是细节是魔鬼。

通常，我会根据$[left, right]$ 和 $[left,right)$ 来分类各种不同的写法。
并且个人更喜欢第二种，而且 $[left, right)$ 也是 C++ stl 中 lower_bound 和 upper_bound 中的使用方法。

1. 返回 [left, right) 内第一个不小于 target 的位置

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    let mid = first + Math.floor((right-left)/2);
    if(arr[mid] < target) left = mid + 1
    else right = mid
  }

  return left;
}

2. 查找 $[left, right)$ 范围里面是否存在值为 target

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    let mid = first + Math.floor((right-left)/2);
    if(arr[mid] < target) left = mid + 1
    else right = mid
  }

  return left < arr.length && arr[left] === target;
}

3. 查找 $[left, right)$ 范围内小于 target 的右边界

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    let mid = first + Math.floor((right-left)/2);
    if(arr[mid] < target) left = mid + 1
    else right = mid
  }

  return left-1;
}

Answer 10

function twoY(arr,str){
var lf=0,rt=arr.length-1,larr,rarr;
while(rt>=lf){
larr=arr[lf],rarr=arr[rt];
if(larr===str && rarr===str||larr==666&&rarr===str||rarr==666&&larr===str){
console.log(lf, rt);
break;
}else if(larr===str&&larr!=666&&rarr!=666){
larr=666;rt--;
}else if(rarr===str&&rarr!=666&&larr!=666){
rarr=666;lf++;
}else if(larr==666&&rarr!==str){
rt--;
}else if(rarr==666&&larr!==str){
lf++;
}else{
rt--;
lf++;
}
}
}
var aa =[1,8,2,3,4,5,11,6,7,8,9,3,2,3];
twoY(aa,11)；
我老了，脑子不是特别好使，瞎jb写的，写的我脑子好难受。

Answer 11

function search(arr, target) {
            let begin = 0;
            let end = arr.length - 1;
            const result = [];
            while (begin <= end) {
                const mid = (begin + end) >>> 1;
                if (target === arr[mid]) {
                    let left = mid;
                    let right = mid;
                    result.push(mid)
                    while (--left && left > 0) {
                        if (arr[mid] === arr[left]) {
                            result.unshift(left)
                        }
                    }
                    while (++right && right < arr.length) {
                        if (arr[mid] === arr[right]) {
                            result.push(right)
                        }
                    }
                    break;
                } else if (target > arr[mid]) {
                    begin = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            return result
        }

// 返回出现目标数据的索引位置数组   第一次出现位置为result[0] 最后一次为 result[result.length -1]

//const list1 = [1, 4, 4, 4, 5, 6, 7];
 //console.log(search(list1, 4));      [1, 2, 3]  第一次出现索引位置为1  最后一次出现的索引位置为3

Answer 12

二分查找基础代码

//递归查找
function erfen_digui(arr, val, left = 0, right = arr.length - 1) {
        if (left > right) {
          return -1;
        }
        let cent = Math.floor((right + left) / 2);
        if (arr[cent] === val) {
          return `最终查找结果下标为${cent}`;
        } else if (arr[cent] > val) {
          right = cent - 1;
        } else {
          left = cent + 1;
        }
        return erfen_digui(arr, val, left, right);
      }
//非递归查找
      function erfen_feidigui(arr, val) {
        let left = 0,
          right = arr.length - 1;
        while (left <= right) {
          let cent = left + Math.floor((right - left) / 2);
          if (arr[cent] === val) {
            return `最终查找结果下标为${cent}`;
          } else if (arr[cent] > val) {
            right = cent - 1;
          } else {
            left = cent + 1;
          }
        }
        return -1;
      }

//左边界查找（查找第一个元素）
function erfen_digui(arr, val, left = 0, right = arr.length - 1) {
        if (left > right) {
          return -1;
        }
        let cent = Math.floor((right + left) / 2);
        if (arr[cent] === val) {
          /****************改动点********************/
          if (arr[cent - 1] === val) {
            right = cent - 1;
          } else {
            return `最终查找结果下标为${cent}`;
          }
          /*****************************************/
        } else if (arr[cent] > val) {
          right = cent - 1;
        } else {
          left = cent + 1;
        }
        return erfen_digui(arr, val, left, right);
      }

// 二分查找右边界（查找最后一个元素）
function erfen_digui(arr, val, left = 0, right = arr.length - 1) {
        if (left > right) {
          return -1;
        }
        let cent = Math.floor((right + left) / 2);
        if (arr[cent] === val) {
          /****************改动点********************/
          if (arr[cent + 1] === val) {
            left = cent + 1;
          } else {
            return `最终查找结果下标为${cent}`;
          }
          /*****************************************/
        } else if (arr[cent] > val) {
          right = cent - 1;
        } else {
          left = cent + 1;
        }
        return erfen_digui(arr, val, left, right);
      }

Answer 13

掘金-神三元的解析: https://juejin.im/post/5d8f6856e51d45784227aca6

Answer 14

详解：https://juejin.im/post/5dd4c4ce6fb9a020350a8c54