二分查找的实现和特性

二分查找前提

• 目标函数单调性（单调递增或者单调递减）
• 存在上下界（bounded）
• 能够通过索引访问（index accessible）

Fast InvSqrt() 扩展阅读

代码实现

function binarySearch (nums) {
  let left = 0,
      right = nums.length - 1;
  
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    const num = nums[mid];

    if (num === target) {
      return mid;
    }
    
    if (num > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return -1;
}

x 的平方根（字节跳动、微软、亚马逊在半年内面试中考过）

有效的完全平方数（亚马逊在半年内面试中考过）

// x 的平方根

/**
 * 二分查找
 * y = x ^ 2，(x > 0)：抛物线，在 y 轴右侧单调递增；存在上下界
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
  if (x == 0 || x == 1) return x;

  let left = 1,
      right = x;

  let mid = 1;

  while (left <= right) {
    mid = left + ((right - left) >> 1);
    
    if (mid * mid > x) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return right;
};


/**
 * 牛顿迭代法
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
  let r = x;

  while (r * r > x) {
    r = ((r + x / r) / 2) | 0;
  }

  return r;
};

// 有效的完全平方数

/**
 * 二分查找
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function(num) {
  let left = 0,
      right = num;

  let mid = 0,
      square = 0;

  while (left <= right) {
    mid = left + ((right - left) >> 1);
    square = mid * mid;
    
    if (square > num) {
      right = mid - 1;
    } else if (square < num) {
      left = mid + 1;
    } else {
      return true;
    }
  }

  return false;
};

搜索旋转排序数组（Facebook、字节跳动、亚马逊在半年内面试常考）

搜索二维矩阵（亚马逊、微软、Facebook 在半年内面试中考过）

寻找旋转排序数组中的最小值（亚马逊、微软、字节跳动在半年内面试中

// 搜索旋转排序数组

/**
 * 将数组二分，比对有序数组，无序数组继续拆分
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  let start = 0,
      end = nums.length - 1;

  let mid = 0;

  while (start <= end) {
    mid = start + ((end - start) >> 1);

    if (nums[mid] === target) return mid;

    if (nums[start] <= nums[mid]) {
      if (nums[start] < target && target < nums[mid]) {
        end = mid - 1;
      } else if (nums[start] === target) {
        return start;
      } else {
        start = mid + 1;
      }
    } else {
      if (nums[mid] < target && target < nums[end]) {
        start = mid + 1;
      } else if (nums[end] === target) {
        return end;
      } else {
        end = mid - 1;
      }
    }
  }

  return -1;
};

// 搜索二维矩阵

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
  const m = matrix.length,
        n = matrix[0].length;

  let left = 0,
      right = m * n - 1;

  let mid = 0;

  while (left <= right) {
    mid = left + ((right - left) >> 1);

    const x = matrix[Math.floor(mid / n)][mid % n];

    if (x < target) {
      left = mid + 1;
    } else if (x > target) {
      right = mid - 1;
    } else {
      return true;
    }
  }

  return false;
};

// 寻找旋转排序数组中的最小值

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
  let left = 0,
      right = nums.length - 1;

  let mid = 0;

  while (left < right) {
    mid = left + ((right - left) >> 1);

    if (nums[mid] < nums[right]) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }

  return nums[left];
};