Dichotomy 二分法

在已从小到大排序的数组（数组内元素均为数字）中找到给定的数字对应的下标

function dichotomySearch(arr, num) {
  var low = 0;
  var high = arr.length - 1;
  var mid = Math.floor((low + high) / 2);

  // while循环的判断条件是high - low > 1
  while (high - low > 1) {
    if (num === arr[low]) {
      return low;
    }
    if (num === arr[high]) {
      return high;
    }
    if (num === arr[mid]) {
      return mid;
    }
    if (num > arr[mid]) {
      low = mid;
      mid = Math.floor((low + high) / 2);
    } else {
      high = mid;
      mid = Math.floor((low + high) / 2);
    }
  }

  // 如果没找到，则返回-1
  return -1;
}

求一个数n的平方根

/**
 * 计算平方根
 * @param  {number} n         需要求平方根的目标数字
 * @param  {number} deviation 偏离度（允许的误差范围）
 * @return {number}           返回平方根
 */
function square(n, deviation) {
  let max = n;
  let min = 0;
  let mid = (max - min) / 2;
  const isAlmost = (val) =>
    val * val - n <= deviation && n - val * val <= deviation;
  while (isAlmost(mid) === false) {
    if (mid * mid > n) {
      max = mid;
      mid = (max + min) / 2;
    } else if (mid * mid < n) {
      min = mid;
      mid = (max + min) / 2;
    }
  }
  return mid;
}