二分法的模版：

类似双指针的操作。

  1. var test = function(nums) {
  2.     let n = nums.length;
  4.     let l = 0;
  5.     let r = n - 1;
  7.     let m = -1; // -1 代表不指向数组里任何一个位置
  8.     while (l <= r) {
  9.         m = l + Math.floor((r - l) / 2);
  11.         if ('has found') {
  12.             return m;
  13.         }
  14.         if ('condition1') {
  15.             l = m + 1;
  16.             continue;
  17.         }
  18.         if ('condition2') {
  19.             r = m;
  20.             continue;
  21.         }
  22.     }
  24.     return -1;
  25. }

367. 有效的完全平方数

但是寻找平方根呢，还有暴力解法：（效果也不差，但是是一点一点去找，比较麻烦）

  1. var isPerfectSquare = function(num) {
  2.     if (num <= 1) {
  3.         return true;
  4.     }
  6.     for (let i = 0; i * i <= num; i++) {
  7.         if (i * i === num) {
  8.             return true;
  9.         }
  10.     }
  12.     return false;
  13. };

以下这个二分法提效，从写法上来说也是双指针：

  1. var isPerfectSquare = function(num) {
  2.     let l = 0;
  3.     let r = num;
  5.     while (l <= r) {
  6.         let m = l + Math.floor((r - l) / 2);
  7.         let square = m * m;
  8.         if (num === square) {
  9.             return true;
  10.         } else if (num < square) {
  11.             r = m - 1;
  12.         } else {
  13.             l = m + 1;
  14.         }
  15.     }
  17.     return false;
  18. };

162. 寻找峰值

这个题的前提，数组之间相邻元素不相同。
不是 和 左右边界比，而是和 相邻左右比较。 ==》 找一种条件可以 二分的形式缩小解的范围

  1. var findPeakElement = function(nums) {
  2.     let n = nums.length;
  4.     let l = 0;
  5.     let r = n - 1;
  7.     let m = -1; // -1 代表不指向数组里任何一个位置
  8.     while (l <= r) {
  9.         m = l + Math.floor((r - l) / 2);
  11.         // 边界处理很帅呀
  12.         let left = (m === 0) ? -Infinity : nums[m - 1];
  13.         let right = (m === n - 1) ? -Infinity : nums[m + 1];
  15.         if (left < nums[m] && nums[m] > right) {
  16.             return m;
  17.         }
  18.         if (nums[m] < right) {
  19.             l = m + 1;
  20.             continue;
  21.         }
  22.         if (nums[m] < left) {
  23.             r = m; // 保留最大值
  24.             // r = m - 1;
  25.             continue;
  26.         }
  27.     }
  29.     return -1;
  30. }

33. 搜索旋转排序数组

image.png
老大哥我费了大力气，终于解出来了，我的思考：就是在找的过程丢掉尽可能多的地方，有效缩小搜索范围。

  1. var search = function(nums, target) {
  2.     let n = nums.length;
  4.     if (n === 0) {
  5.         return -1;
  6.     }
  7.     if (n === 1) {
  8.         return nums[0] === target ? 0 : -1;
  9.     }
  11.     // 1、先去找转折点
  12.     let l = 0;
  13.     let r = n - 1;
  15.     let m = -1; // -1 代表不指向数组里任何一个位置
  16.     while (l <= r) {
  17.         m = l + Math.floor((r - l) / 2);
  19.         if (nums[m] === target) {
  20.             return m;
  21.         }
  23.         if (nums[l] <= nums[m]) { // 隔出有序区间[l...m]
  24.             if (nums[l] <= target && target < nums[m]) { // 在 有序区间[l...m] 中
  25.                 r = m - 1;
  26.             } else {
  27.                 l = m + 1;
  28.             }
  29.         } else { // 隔出有序区间[m...r]
  30.             if (nums[m] < target && target <= nums[r]) { // 在 有序区间[m...r] 中
  31.                 l = m + 1;
  32.             } else {
  33.                 r = m - 1;
  34.             }
  35.         }
  37.     }
  39.     return -1;
  40. };

74. 搜索二维矩阵

// 加强版 二分搜索