二分法

前提：数组已预先排序。目标：查找数组中指定数字的坐标（0-based）。二分法通俗点说，就是对一个已经事先排序过的数组，设置分别指向数组首尾两头的首尾游标，然后根据首尾游标的位置设定中间点游标，由于数组已经排序过了，可以通过比较给定数字与三个游标的大小关系来不断的更新首尾中三个游标的位置，这个过程中只要收尾中三个游标对应的数字有一个等于给定数字，或者首尾游标的位置中间仅剩一个游标位，就可以拿到给定数字对应的位置的。

function binarySearch(arr, num) {
  // assume arr has been sorted in advance
  var low = 0;
  var high = arr.length - 1;
  var mid = Math.floor((low + high) / 2);

  // 循环的终止条件是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);
    }
  }

  // if not found
  return -1;
}

二分法 ​

二分法