https://labuladong.gitee.io/algo/2/21/57/

模板

左右闭区间的比较好理解

算法

const binarySearch = function (nums, target) {
      if (nums.length === 0) return -1;
    var left = 0, right = nums.length - 1;// 注意
      var mid;
    while (left <= right) {
        var mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) return mid
        else if (nums[mid] < target) left = mid + 1;// 注意
        else if (nums[mid] > target) right = mid - 1;// 注意
    }
    return -1;
}

while为啥是<= ：因为right的初始值为length-1 ; while 的终止条件为left == right+1的时候，这个时候表示搜索完毕
为什么是left = mid +1 和 right = mid - 1 ,因为本算法的搜索区间是左右闭区间[left , right] ```javascript 因为我们初始化 right = nums.length - 1 所以决定了我们的「搜索区间」是 [left, right] 所以决定了 while (left <= right) 同时也决定了 left = mid+1 和 right = mid-1

因为我们只需找到一个 target 的索引即可所以当 nums[mid] == target 时可以立即返回

引申：
> 比如说给你有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3。
<a name="MbUIE"></a>
## 求左边界
```javascript
const left_binarySearch = function(nums, target) {
  if (nums.length === 0) return -1;
  var left = 0,
    right = nums.length - 1;
  var mid;
  while (left <= right) {
    console.log(left + "-" + right);
    var mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) right = mid - 1;  // 别返回，锁定左侧边界
    else if (nums[mid] < target) left = mid + 1;
    else if (nums[mid] > target) right = mid - 1;
  }
  if (left >= nums.length || nums[left] != target) return -1; // 最后要检查越界的情况
  return left;
};

===的时候，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid-1]中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。
由于 while 的退出条件是 left == right + 1，所以当 target 比 nums 中所有元素都大时，会存在索引越界

求右边界

const right_binarySearch = function(nums, target) {
  if (nums.length === 0) return -1;
  var left = 0,
    right = nums.length - 1;
  var mid;
  while (left <= right) {
    console.log(left + "-" + right);
    var mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) left = mid + 1;   // 别返回，锁定右侧边界
    else if (nums[mid] < target) left = mid + 1;
    else if (nums[mid] > target) right = mid - 1;
  }
  if (right < 0 || nums[right] != target) return -1; // 最后要检查越界的情况
  return right;
};

总结

如需定义左闭右开的「搜索区间」搜索左右边界，，right 不需要+1 ，只要在 nums[mid] == target 时做修改即可，搜索右侧时需要减一 ```javascript //左闭右开 var search = function (nums, target) {
```
if (nums.length === 0) return -1;
```
var left = 0, right = nums.length;
```
var mid;
```
while (left < right) {
```
  var mid = Math.floor((left + right) / 2);
  if (nums[mid] === target) return mid
  else if (nums[mid] < target) left = mid + 1;
  else if (nums[mid] > target) right = mid ;
```
} return -1; };

//左边界 var Lsearch = function (nums, target) { if (nums.length === 0) return -1; var left = 0, right = nums.length; var mid; while (left < right) { var mid = Math.floor((left + right) / 2); if (nums[mid] === target) right = mid; else if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right; } if (left >= nums.length || nums[left] != target) return -1; return left };

//右边界 var Rsearch = function (nums, target) { if (nums.length === 0) return -1; var left = 0, right = nums.length; var mid; while (left < right) { var mid = Math.floor((left + right) / 2); if (nums[mid] === target) left = mid + 1; else if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right; } if (right < 0 || nums[right] != target) return -1; return right -1 ; };

<a name="ktcIK"></a>
# 题
<a name="RllWR"></a>
## 704
> <a name="Ea55L"></a>
#### [704. 二分查找](https://leetcode-cn.com/problems/binary-search/)
> 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

```javascript
略

34

34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

第一种方法：调用上面的两个左右边界的方法

const left_binarySearch = function (nums, target) {...}
const right_binarySearch = function (nums, target) {...}
var searchRange = function (nums, target) {
    return [left_binarySearch(nums, target),right_binarySearch(nums, target)]
};

可以把左右两种算法结合下逻辑：876

const binarySearch = (nums, target, lower) => {
    let left = 0, right = nums.length - 1, ans = nums.length;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > target || (lower && nums[mid] >= target)) {
            right = mid - 1;
            ans = mid;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

var searchRange = function(nums, target) {
    let ans = [-1, -1];
    const leftIdx = binarySearch(nums, target, true);
    const rightIdx = binarySearch(nums, target, false) - 1;
    if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] === target && nums[rightIdx] === target) {
        ans = [leftIdx, rightIdx];
    } 
    return ans;
};

875

875. 爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

输入: piles = [3,6,7,11], H = 8
输出: 4

//如果用暴力法,会超时
const minEatingSpeed2 = function (piles, h) {
    const max = Math.max(...piles);
    for (let i = 1; i < max; i++) {
        if (canFinish(piles, i, h))
            return i;
    }
    return max;
};

这个 for 循环，就是在连续的空间线性搜索，这就是二分查找可以发挥作用的标志。由于我们要求的是最小速度，所以可以用一个搜索左侧边界的二分查找来代替线性搜索，提升效率。1011 ```javascript const minEatingSpeed = function (piles, h) { // 套用搜索左侧边界的算法框架 let left = 1,
```
  right = Math.max(...piles);
```
while (left <= right) {
```
  // 防止溢出
  let mid = left + Math.floor((right - left) / 2);
  if (canFinish(piles, mid, h)) right = mid - 1;
  else left = mid + 1;
```
} return left; };

// 时间复杂度 O(N) const canFinish = (piles, speed, H) => { let time = 0; piles.forEach((p) => (time += Math.ceil(p / speed))); return time <= H; };

<a name="mAtVD"></a>
## 1011
> <a name="eJnTH"></a>
#### [1011. 在 D 天内送达包裹的能力](https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/)
> 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
> 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
> 
> 返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
> 
> **输入**：weights = [3,2,2,4,1,4], D = 3输出：6
> **解释**：
> 船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
> 第 1 天：3, 2
> 第 2 天：2, 4
> 第 3 天：1, 4

```javascript
const shipWithinDays = function (weights, D) {
    // 套用搜索左侧边界的算法框架
    let left = Math.max(...weights), right = weights.reduce((a, b) => a + b);
    while (left <= right) {
        let day = 1, datWeight = 0
        // 防止溢出
        let mid = left + Math.floor((right - left) / 2);
        if (canTrans(weights, mid, D)) right = mid - 1;
        else left = mid + 1;
    }
    return left;
};
const canTrans = (weights, mid, D) => {
    let day = 1, dayWeight = 0
    for (const weight of weights) {
        if (dayWeight + weight > mid) {
            day++;
            dayWeight = 0;
        }
        dayWeight += weight;
    }
    return day <= D;
};

技巧：

确定两分查找的左右区间
确定满足条件的边界

刷个算法

二分查找问题

模板

算法

求右边界

总结

34

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

875

875. 爱吃香蕉的珂珂