二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

英语科普：二分法，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
    } else if (num === arr[high]) {
      return high
    } else if (num === arr[mid]) {
      return mid
    } else 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  {[type]} n         需要求平方根的目标数字
 * @param  {[type]} deviation 偏离度（允许的误差范围）
 * @return {[type]}           返回平方根
 */
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
}