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
}