Skip to content

二分搜索

前提

  • 数组必须有序
  • 输入可以是数组，也可以是一个区间的起止位置
  • 时间复杂度 O(logn)

递归写法

function binarySeach(arr, target, low, high) {
  if (low > high) {
    return -1;
  }

  let middle = low + Math.floor((high - low) / 2);

  if (arr[middle] === target) {
    return middle;
  }

  if (target > arr[middle]) {
    return binarySeach(arr, target, middle + 1, high);
  } else {
    return binarySeach(arr, target, low, middle - 1);
  }
}

正常迭代写法

function binarySeach(arr, target, low, high) {
  while(low <= high) {
    let middle = low + Math.floor((high - low) / 2);

    if (arr[middle] === target) {
      return middle;
    }

    if (target > arr[middle]) {
      low = middle + 1;
    } else {
      high = middle - 1;
    }
  }

  return -1;
}