Js 二分查找

发布于:2023-05-09 ⋅ 阅读:(237) ⋅ 点赞:(0)
先玩一个小游戏。预先给定一个小于100的正整数x,让你猜,猜测过程中给予大小判断的提示,问你怎样快速地猜出来? 这样猜测最快,先猜50,如果猜对了,结束;如果猜大了,往小的方向猜,再猜25;如果猜小了,往大的方向猜,再猜75;…,每猜测1次就去掉一半的数,就这样可以逐步逼近预先给定的数字。这种思想就是二分法。

经典例题:使用二分法在数组中查找指定值的位置

function findIdx(arr,target){
  let left = 0;
  let right = arr.length - 1;
  let mid;
  while(left <= right){
    mid = Math.ceil((left + right)/2);
    if(arr[mid] === target){
      return mid;
    }
    if(arr[mid] > target){
      right = mid - 1;
    }
    if(arr[mid] < target){
      left = mid + 1
    }
  }
  return -1;
}
var arr = [1, 2, 3, 4, 5, 6, 7, 9, 10, 34, 35, 66];
console.log( findIdx(arr, 66));//11