二分查找法🍉

题目信息

在有序列表中查找一个数的下标

问题解答

找个中值mid作为参考
如果中值mid大于目标元素，就将下一次的最大值high赋值为mid - 1
如果中值mid小于目标元素，就将下一次的最大值low赋值为mid + 1

非递归

function binarySeach(arr: number[], target: number) {
    let low = 0,
      high = arr.length - 1
     while(low <= high) {
      let mid = Math.floor((low + high) / 2)
    if(arr[mid] === target) {
      return mid
    }
    if(arr[mid] > target) {
      high = mid - 1
    }
    if(arr[mid] < target) {
        low = mid + 1
    }
  }
  return -1
}

递归

function binarySeach(arr: numer[], low: num, high:[], target) {
    if(low > high) {
      return -1
  }

  let mid = Math.floor((low + high) / 2)

  if(arr[mid] === target) {
      return mid
  }

  if(arr[mid] > target) {
      return binarySeach(arr, low, mid - 1, target)
  }

  if(arr[mid] < target) {
      return binarySeach(arr, mid + 2, high, target)
  }
}