Allen's blog
Allen
2023-02-14
目录

二分查找

力扣题目链接 (opens new window)、代码随想录链接 (opens new window)

# 题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
1
2
3

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
1
2
3

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

# 总结

  1. 二分法查找前提条件

    1. 有序数组
    2. 无重复元素

  2. 二分法边界条件

    大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

    写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

    1. 左闭右闭 定义 target 在[left, right]区间

      • while (left <= right) 要使用 <= ，因为 left == right 是有意义的，所以使用 <=
      • if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个 nums[middle]一定不是 target，那么接下来要查找的左区间结束下标位置就是 middle - 1

    2. 左闭右开 定义 target 是在一个在左闭右开的区间里，也就是[left, right)

      • while (left < right)，这里使用 < ,因为 left == right 在区间[left, right)是没有意义的
      • if (nums[middle] > target) right 更新为 middle，因为当前 nums[middle]不等于 target，去左区间继续寻找，而寻找区间是左闭右开区间，所以 right 更新为 middle，即：下一个查询区间不会去比较 nums[middle]

  3. middle = left + ((right - left) / 2) // 防止溢出 等同于(left + right)/2C++中，整型除法得到的是商的整数部分

  4. 思路：

    1. 定义 left 索引、right 索引
    2. 循环：结束条件为 nums[left]>nums[right]注意边界
    3. 计算 middle，判断 nums[middle]和 target 的大小，并更新 left 和 right 的值注意边界
    4. 如果循环结束还未找到，则返回“未找到”

# 练习题

# 35.搜索插入位置 (opens new window)

# 思路

  1. 分析插入目标值有哪几种情况
    1. 目标值在数组所有元素之前
    2. 目标值等于数组中某一个元素
    3. 目标值插入数组中的位置
    4. 目标值在数组所有元素之后
  2. 暴力解法
    class Solution {
public:
 int searchInsert(vector<int>& nums, int target) {
     for (int i = 0; i < nums.size(); i++) {
     // 分别处理如下三种情况
     // 目标值在数组所有元素之前
     // 目标值等于数组中某一个元素
     // 目标值插入数组中的位置
         if (nums[i] >= target) { // 一旦发现大于或者等于target的num[i]，那么i就是我们要的结果
             return i;
         }
     }
     // 目标值在数组所有元素之后的情况
     return nums.size(); // 如果target是最大的，或者 nums为空，则返回nums的长度
 }
};
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
  3. 二分法 既然暴力解法的时间复杂度是 O(n)，就要尝试一下使用二分查找法。 本题满足二分法基础条件：有序数组、无重复 (时间复杂度 O(logn)、空间复杂度 O(1))
    class Solution {
public:
  int searchInsert(vector<int>& nums, int target) {
      int n = nums.size();
      int left = 0;
      int right = n - 1; // 定义target在左闭右闭的区间里，[left, right]
      while (left <= right) { // 当left==right，区间[left, right]依然有效
          int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
          if (nums[middle] > target) {
              right = middle - 1; // target 在左区间，所以[left, middle - 1]
          } else if (nums[middle] < target) {
              left = middle + 1; // target 在右区间，所以[middle + 1, right]
          } else { // nums[middle] == target
              return middle;
          }
      }
      // 分别处理如下四种情况
      // 目标值在数组所有元素之前  [0, -1]
      // 目标值等于数组中某一个元素  return middle;
      // 目标值插入数组中的位置 [left, right]，return  right + 1
      // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
      return right + 1;
  }
};
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
  4. 我编写的
    var searchInsert = function (nums, target) {
    let left = 0,
        right = nums.length - 1,
        middle = 0
    while (left <= right) {
        middle = left + Math.floor((right - left) / 2)
        if (nums[middle] > target) {
            right = middle - 1
            if (right == -1) return 0
            if (nums[right] < target) {
                return right + 1
            }
        } else if (nums[middle] < target) {
            left = middle + 1
            if (left == nums.length) return left
            if (nums[left] > target) {
                return left
            }
        } else {
            return middle
        }
    }
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23

# 总结

先写二分法查找的代码，注意循环不变量。 写完查找代码后再添加判断逻辑。我的代码的判断应该放在循环之外，循环表示的是相等的情况，同时也表示不相等，最后 left 会大于 right，这个就是 target 位于数组中间的情况。

我在最开始没分析好 target 出现在数组中的情况，没有分析好判断逻辑，虽然完成了任务，但是思路不够清晰。

# 34.在排序数组中查找元素的第一个和最后一个位置 (opens new window)

# 思路

我的解决方案：

采用二分法查找 target 是否在数组中

  1. 如果没有在数组中，返回[-1,-1]
  2. 如果在数组中,获取到二分法查找结果，然后在左右搜索相等的值，直到不相等，即找到边界

方案二：耗时最少 寻找 target 在数组里的左右边界，有如下三种情况：

  1. 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target 为 2 或者数组{3, 4, 5},target 为 6，此时应该返回{-1, -1}
  2. 情况二：target 在数组范围中，且数组中不存在 target，例如数组{3,6,7},target 为 5，此时应该返回{-1, -1}
  3. 情况三：target 在数组范围中，且数组中存在 target，例如数组{3,6,7},target 为 6，此时应该返回{1, 1}

分析： 第一种情况下，leftBorder 或者 rightBorder 必定有一个是初始值-2，即判断条件为if(leftBorder === -2 || rightBorder === -2) return [-1,-1]; 第二种情况下，leftBorder - rightBorder 等于 1, 这个要画图理解，[2,4,8,9,13]，target=6，最后的 leftBorder=1，rightBorder=2 第三种情况下，rightBorder - leftBorder必定大于 1？因为最后的结果是[leftBorder + 1, rightBorder - 1],leftBorder 和 rightBorder 至少相差 2 才行。

方案三：

  1. 首先，在 nums 数组中二分查找得到第一个大于等于 target 的下标（左边界）与第一个大于 target 的下标（右边界）；
  2. 如果左边界<= 右边界，则返回 [左边界, 右边界]。否则返回[-1, -1]

方案四：

  1. 首先，在 nums 数组中二分查找得到第一个大于等于 target 的下标 leftBorder；
  2. 在 nums 数组中二分查找得到第一个大于等于 target+1 的下标， 减 1 则得到 rightBorder；
  3. 如果开始位置在数组的右边或者不存在 target，则返回[-1, -1] 。否则返回[leftBorder, rightBorder]

# 总结

这道题我的思路还停留在寻找插入位置的思路，即先使用二分法查找，再根据查找过程或者结果进行判断，属于是没掌握精髓（区间缩窄，理清边界）。 使用二分法，left、middle、right 是怎么在流动（实际是在分析查找区间）？怎么实现在 nums 数组中二分查找得到第一个大于等于 target 的下标（左边界）与第一个大于 target 的下标（右边界）？下面进行区间缩窄分析：

分为几种情况：

  1. target 不在数组范围内 这种情况，left 或者 right 必然有一个是停留在原位置的

    • 当 target 在数组右侧，right 在整个循环过程不改变，left 会一直更新，leftBorder 也一直更新，最后 leftBorder = nums.length, rightBorder = -2
    • 当 target 在数组左侧，left 在整个循环过程不改变，right 会一直更新，rightBorder 也一直更新，最后 leftBorder = -2 ,rightBorder = -1

    当前情况的判断条件为：rightBorder == -2 || leftBorder == -2

  2. target 在数组范围内

    1. 在数组中 在二分法查找的算法中，nums[middle] == target 就退出循环了，但是这样不能寻找 target 边界，因此要不停缩窄 leftBorder 和 rightBorder 知道区间不存在 target，采取的方案是：

      • 找 leftBorder：当 nums[middle] == target 时，right = middle - 1 可以选取左侧区间，right 会不断往左走，直到缩窄后的区间没有 target 时，right 不再变化，值为最左边的 target 的前一个索引，这个就是 leftBorder。
      • 找 rightBorder：当 nums[middle] == target 时，left = middle + 1 可以选取右侧区间，left 会不断往右走，直到缩窄后的区间没有 target 时，left 不再变化，值为最右边的 target 的后一个索引，这个就是 rightBorder。

      这种情况下，rightBorder - leftBorder > 1

    2. 不在数组中 通过画图理解，rightBorder - leftBorder == 1

# 69.x 的平方根 (opens new window)

# 思路

采用二分法，不断缩小查找区间。 我最开始的实现方式是在二分法查找过程中进行判断，最后结果是耗时较长。 优化方案是在二分法查找结束后进行判断，如果找到刚好平方等于 x 的，就直接返回；如果二分法没有找到，那么 x 的算数平方根会最后会在 left 和 right 之间，由于题目要求向下取整，即 return left 第一次代码：

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
    let left = 0,
        right = x,
        middle
    while (left <= right) {
        middle = left + Math.floor((right - left) / 2)
        let middlePower = middle * middle
        if (middlePower > x) {
            if ((middle - 1) ** 2 <= x) return middle - 1
            right = middle - 1
        } else {
            if ((middle + 1) ** 2 > x) return middle
            if ((middle + 1) ** 2 == x) return middle + 1
            left = middle + 1
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

优化后的代码：

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
    let left = 0,
        right = x,
        middle,
        searchResult = null
    while (left <= right) {
        middle = left + Math.floor((right - left) / 2)
        let middlePower = middle * middle
        if (middlePower > x) {
            if ((middle - 1) ** 2 <= x) return middle - 1
            right = middle - 1
        } else if (middlePower < x) {
            left = middle + 1
        } else {
            searchResult = middle
            break
        }
    }
    if (searchResult != null) return middle
    return left
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 367.有效的完全平方数 (opens new window)

这一题和上一题如出一辙。 初始代码

/**
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function (num) {
    let left = 0,
        right = num,
        middle
    while (left <= right) {
        middle = left + Math.floor((right - left) / 2)
        const power = middle * middle
        if (power > num) {
            right = middle - 1
        } else if (power < num) {
            left = middle + 1
        } else {
            return true
        }
    }
    return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

优化了 right 的值：

/**
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function (num) {
    let left = 0,
        right = Math.floor(num / 2),
        middle
    if (num == 1) return 1
    while (left <= right) {
        middle = left + Math.floor((right - left) / 2)
        const power = middle * middle
        if (power > num) {
            right = middle - 1
        } else if (power < num) {
            left = middle + 1
        } else {
            return true
        }
    }
    return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
上次更新: 2023/12/16, 09:22:46
数组理论基础
移除元素

← 移除元素→

最近更新
01
rollup使用配置文件rollup.config.ts打包
12-08
02
package.json导出类型
12-08
03
关键问题方案
11-17
更多文章>
Theme by Vdoing | Copyright © 2023-2023 Allen | Github