属于双指针的一种典型应用。

前提： 无重复元素，（必须）递增。

二分查找对具有指定左索引和右索引的连续序列进行操作。与中间索引对比，改变左/右指针从而缩小一般的查找空间。

时间：O(log n) —— 算法时间

空间：O(1) —— 常量空间

leetcode二分

练习：

剑指 Offer 53 - II. 0～n-1中缺失的数字

  1. var missingNumber = function(nums) {
  2.     let left = 0;
  3.     let right = nums.length - 1;
  4.     while (left < right) {
  5.         let mid = Math.floor((left + right) / 2);
  6.         let cur = nums[mid]
  7.         if (cur == mid) {
  8.             left = mid + 1;
  9.         } else {
  10.             right = mid
  11.         }
  12.     }
  13.     return left == nums[left] ? nums.length : left // 细节处理
  14. };

用例： [0]、[0,2]

剑指 Offer 11. 旋转数组的最小数字（支持重复）

⚠️ 以左边为判断依据， 相等情况下仅移动一位

var minArray = function(numbers) {
    let left = 0;
    let right = numbers.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (numbers[mid] > numbers[right]) {
            left = mid + 1;
        } else if (numbers[mid] < numbers[right]) {
            right = mid
        } else {
            right--;
        }
    }
    return numbers[left]
};

练习1:

标准的二分查找模板

  • 不与两侧比较
  • 仅比较， 不做后处理， 至到底部

伪代码

  • 初始条件：left = 0, right = length-1
  • 终止：left > right
  • 向左查找：right = mid-1
  • 向右查找：left = mid+1

704. 二分查找

function search(nums: number[], target: number): number {
    if (nums.length == 0) return -1;
    if (nums.length == 1) return nums[0] == target ? 0 : -1;
    let left: number = 0;
    let right: number = nums.length - 1;
    while (left <= right) {
        let mid: number = Math.floor((left + right) / 2);
        let cur = nums[mid];
        if (cur == target) {
            return mid;
        } else if (cur > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
};

744. 寻找比目标字母大的最小字母

case

console.log(nextGreatestLetter( ["c", "f", "j"], 'a'));
console.log(nextGreatestLetter( ["c", "f", "j"], 'j'));
console.log(nextGreatestLetter( ["c", "f", "j"], 'g'));
// c
// c
// j

注意： 非法校验

function nextGreatestLetter(letters: string[], target: string): string {
    let n = letters.length;
    let x = target.charCodeAt(0);
    if (x >= letters[n - 1].charCodeAt(0)) return letters[0];

    let left = 0, right = letters.length - 1;
    while (left < right) {
        let mid = (left + right) >> 1;
        if (x < letters[mid].charCodeAt(0)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return letters[left];
};

268. 丢失的数字

var missingNumber = function(nums) {
    nums.sort((a, b) => a - b);
    let left = 0;
    let right = nums.length-1;
    let mid = Math.round((left + right) / 2);
    while (nums.includes(mid)) {
        if (nums[mid] == mid) {
            left = mid+1;
        } else  {
            right = mid-1;
        }
        mid = Math.round((left + right) / 2);
    }
    return mid;
};

374. 猜数字大小

var guessNumber = function(n) {
    let left = 1;
    let right = n;
    while (left <= right) {
        let middle = Math.floor((left + right) / 2)
        let curRes = guess(middle)
        if (curRes == 0) {
            return middle
        } else if (curRes < 0) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return middle
};

33. 搜索旋转排序数组

function search(nums: number[], target: number): number {
    if (nums.length == 0) return -1;
    let left: number = 0;
    let right: number = nums.length -1;
    while (left <= right) {
        let mid: number = Math.floor((left + right) / 2);
        let midNum: number = nums[mid];
        if (midNum == target) {
            return mid
        } else if (nums[left] <= midNum) {
            // 左侧为升序
            if (nums[left] <= target && target < midNum) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // 右侧为升序
            if (midNum < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
};

练习2:（高级方法）

  • 需要访问元素的直接右邻居
  • 每一步中至少有 2 个元素
  • 剩下 1 个元素时，循环 / 递归结束

伪代码：

  • 初始条件：left = 0, right = length
  • 终止：left == right
  • 向左查找：right = mid
  • 向右查找：left = mid+1

278. 第一个错误的版本

[1, n]区间二分， left == right， 返回任意值均可。 注意除2 使用 >> 1会超时， 使用>>> 1

var solution = function(isBadVersion: any) {

    return function(n: number): number {
        let left = 1, right = n;
        while (left < right) {
            let mid = (left + right) >>> 1;
            let valied = isBadVersion(mid);
            if (valied) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // return right; // 均可
        return left;
    };
};

162. 寻找峰值

读题关键： 假设 nums[-1] = nums[n] = -∞
left = right
return left/right

function findPeakElement(nums: number[]): number {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let mid: number = (left + right) >> 1;
        if (nums[mid] <= nums[mid+1]) {
            left = mid +1;
        } else {
            right = mid;
        }
    }
    return left;
};

540. 有序数组中的单一元素

function singleNonDuplicate(nums: number[]): number {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let mid = (left + right) >> 1;
        if ((mid & 1) == 1) --mid;
        if (nums[mid] == nums[mid + 1]) {
            left = mid + 2;
        } else {
            right = mid;
        }
    }
    return nums[left];
};

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

function findMin(nums: number[]): number {
    let left: number = 0;
    let right: number = nums.length -1;
    while (left < right) {
        let mid: number = Math.floor((left + right) / 2);
        if (nums[mid] > nums[right]) {
            left = mid +1;
        } else {
            right = mid;
        }
    }
    return nums[right];
};

练习3:（独特形式）

  • 需要访问元素的直接左右邻居
  • 每个步骤中至少有 3 个元素
  • 当剩下 2 个元素时，循环 / 递归结束

伪代码：

  • 初始条件：left = 0, right = length-1
  • 终止：left + 1 == right
  • 向左查找：right = mid
  • 向右查找：left = mid

34. 在排序数组中查找元素的第一个和最后一个位置

寻找左侧边界

left = 0
right = nums.length
while (left < right) {
    if (mid == target) {
      right = mid
  } else (mid < target) {
      left = mid +1;
  } else {
      right = mid;
  }
}
return left

寻找右侧边界

left = 0
right = nums.length
while (left < right) {
    if (mid == target) {
      // right = mid
    left = mid+1;
  } else (mid < target) {
      left = mid +1;
  } else {
      right = mid;
  }
}
return left - 1;

关键： 合并左右边界查找在一个函数中

function searchRange(nums: number[], target: number): number[] {
    let res: number[] = [-1, -1];
    let firstIndex: number = helper(nums, target, true);

    if (firstIndex == nums.length || nums[firstIndex] != target) {
        return res;
    }

    res[0] = firstIndex;
    res[1] = helper(nums, target, false)-1;

    return res;
};

function helper(nums: number[], target: number, isFirst: boolean) {
    let left: number = 0;
    let right: number = nums.length;

    while (left < right) {
        let mid: number = Math.floor((left + right) / 2);
        let midNum: number = nums[mid];
        if (midNum > target) {
            right = mid;
        } else if (isFirst && midNum == target) {
            right = mid;
        } else {
            left = mid+1;
        }
    }

    return left;
}

658. 找到 K 个最接近的元素

练习4：双数组的二分查找

4. 寻找两个正序数组的中位数

练习5:

50. Pow(x, n)

367. 有效的完全平方数

744. 寻找比目标字母大的最小字母

练习6:

weekly:

5764. 准时到达的列车最小时速

 var minSpeedOnTime = function(dist, hour) {
   if (dist.length > Math.ceil(hour)) return -1;
   let left = 1, right = 10 ** 7;
   while (left < right) {
       let mid = (left + right) >> 1;
       if (arriveOnTime(dist, mid, hour)) {
           right = mid;
       } else {
           left = mid + 1;
       }
   }
   return left;
};

function arriveOnTime (dist, speed, hour) {
   let res = 0.0;
   let n = dist.length;
   for (let i = 0; i < n; i++) {
       let cost = parseFloat(dist[i]) / speed;
       if (i != n - 1) {
           cost = Math.ceil(cost);
       }
       res += cost;
   }
   return res <= hour;
}

1889. 装包裹的最小浪费空间

function minWastedSpace(packages: number[], boxes: number[][]): number {
    const MOD = 10 ** 9 + 7;
    packages.sort((a, b) => a - b);
    const max_package = packages[packages.length - 1];
    const total = packages.reduce((a, c) => a + c, 0);
    let res = Infinity;
    for (let box of boxes) {
        box.sort((a, b) => a - b);
        if (max_package > box[box.length - 1]) continue;
        let left = 0, sum = 0;
        for (let capacity of box) {
            let right = searchRight(packages, capacity, left);
            sum += (right - left) * capacity;
            left = right;
        }
        res = Math.min(res, sum);
    }
    return res == Infinity ? -1 : (res - total) % MOD;
};

辅助函数

function searchRight(packages: number[], target: number, left: number): number {
    let right = packages.length;
    while (left < right) {
        let mid = (left + right) >> 1;
        if (packages[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

console.log(searchRight([3,5,8,10,11,12], 10, 0));
// 4

mid特殊处理的二分

69. x 的平方根

function mySqrt(x: number): number {
    if (x == 0) return 0;
    let left = 1, right = x;
    while (left < right) {
        let mid = left + ((right - left + 1) >> 1);
        if ((mid ** 2) <= x) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
};

标记

1760. 袋子里最少数目的球

Minimum Light Radius

常规方法

function solve(nums: Array<number>): number {
    const n = nums.length;
    if (n <= 3) return 0;
    nums.sort((a, b) => a - b);
    let left = 0, right = nums[n - 1] - nums[0];
    while (left <= right) {
      let mid = (left + right) >> 1;
      if (isCover(nums, mid)) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return left / 2;
}

function isCover(nums: Array<number>, radius: number): boolean {
  let left = nums[0], right = left + radius;
  for (let i = 0; i < 3; i++) {
    let j = searchRight(nums, right);
    if (j >= nums.length) return true;
    left = nums[j], right = left + radius;
  }
  return false;
}

function searchRight(nums: number[], target: number, left: number = 0, right: number = nums.length): number {
  if (left < 0) throw ('left must be non-negative');
  while (left < right) {
      let mid = (left + right) >> 1;
      if (target < nums[mid]) {
          right = mid;
      } else {
          left = mid + 1;
      }
  }
  return left;
}

console.log(solve([3, 4, 5, 6]));
// 0.5

其他方法

function solve(nums: Array<number>): number {
    if (!nums.length) return 0;
    const n = nums.length;
    nums.sort((a, b) => a - b);
    let left = 0, right = nums[n - 1] - nums[0];
    for (let i = 0; i < 40; i++) {
      let mid = (left + right) / 2;
      if (validate(nums, mid) <= 3) {
        right = mid;
      } else {
        left = mid;
      }
    }
    return right;
}

function validate(nums: Array<number>, radius: number): number {
  let ans = 0;
  for (let i = 0; i < nums.length; ) {
    ans++;
    let distance = nums[i] + 2 * radius;
    let j = i + 1;
    while (j < nums.length && nums[j] <= distance) j++;
    i = j;
  }
  return ans;
}

console.log(solve([3, 4, 5, 6]));

参考：

https://leetcode-cn.com/leetbook/detail/binary-search/

https://mp.weixin.qq.com/s/uA2suoVykENmCQcKFMOSuQ