基础 #

/**
 * 二分查找
 * @param arr 查找的数组
 * @param x 查找的元素
 * @returns 查找到返回数组下标，否则返回-1
 */
function binarySearch(arr, x) {
  let low = 0 // 首下标
  let high = arr.length - 1 // 尾下标
  // 只要查找区间起始点和结束点中间还有值(要包括两值相同的情况)，就继续进行查找
  while (low <= high) {
    const mid = (low + high) / 2 // 确定中间值下标
    //如果查找值等于中间值
    if (x == arr[mid]) {
      return mid // 则这个mid值，就是查找到的数组下标
    }
    //如果查找值小于中间值
    else if (x < arr[mid]) {
      high = mid - 1 // 则在左半部分查找，需要重新确认区间high的位置
    }
    // 否则查找值大于中间值
    else {
      low = mid + 1 // 则在右半部分查找，需要重新确认区间low的位置
    }
  }
  return -1 //没有查找到，返回-1
}
const arr = [1, 3, 5, 6, 7, 8, 9]
const x = 7
console.log(binarySearch(arr, x))

/**
 * 二分查找
 * @param arr 查找的数组
 * @param x 查找的元素
 * @returns 查找到返回数组下标，否则返回-1
 */
function binarySearch(arr, x) {
  let low = 0 // 首下标
  let high = arr.length - 1 // 尾下标
  // 只要查找区间起始点和结束点中间还有值(要包括两值相同的情况)，就继续进行查找
  while (low <= high) {
    const mid = (low + high) / 2 // 确定中间值下标
    //如果查找值等于中间值
    if (x == arr[mid]) {
      return mid // 则这个mid值，就是查找到的数组下标
    }
    //如果查找值小于中间值
    else if (x < arr[mid]) {
      high = mid - 1 // 则在左半部分查找，需要重新确认区间high的位置
    }
    // 否则查找值大于中间值
    else {
      low = mid + 1 // 则在右半部分查找，需要重新确认区间low的位置
    }
  }
  return -1 //没有查找到，返回-1
}
const arr = [1, 3, 5, 6, 7, 8, 9]
const x = 7
console.log(binarySearch(arr, x))