算法笔记：二分查找

拼搏现实的明天。 2024-03-27 15:24 44阅读 0赞

### 1 二分查找 ###

#### 1.1 概念 ####

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查找以空的一半结束，则无法满足条件，并且无法找到目标。

#### 1.2 时间复杂度 O(log n) ####

假设总共有`n`个元素，则第一次查找剩余`n/2`个元素，第二次查找剩余`n/2/2`个元素，然后是`n/2/2/2`、`n/2/2/2/2`以此类推。

假设总共查找了`k`次，则剩余`n/2^k`个元素。最坏的情况是查找到最后一个元素，则有等式：`n/2^k=1`，即`2^k=n`，得：k=log2n

忽略常数，则二分查找的时间复杂度为`O(log n)`

#### 1.3 二分查找与顺序查找对比图 ####

![请添加图片描述][c25c46a47dc84db180bccf544f6106b5.gif]

注：顺序查找时间复杂度为`O(n)`

### 2 二分查找的一般步骤 ###

*  第一步：如果集合未排序，则进行排序；
 *  第二步：使用循环或递归在每次比较后将查找空间划分为两半；
 *  第三步：在剩余空间中确定可行的候选者。

### 3 二分查找常用模板 ###

#### 3.1 模板1：搜索区间左闭右闭，基本的二分查找 ####

int binarySearch(int[] nums, int target) {
        
        if (nums == null || nums.length == 0) return -1;
        int left = 0;
        int right = nums.length - 1;// 搜索区间为[left,right]，两端都闭，nums.length 下标越界，故而使用最后一个元素的索引 nums.length - 1
        while (left <= right) {
        // 循环终止条件: left == right + 1，搜索区间为空，终止循环
            int mid = left + (right - left) / 2;// 防止(left + right)溢出
            if (nums[mid] == target) {
        
                return mid;
            } else if (nums[mid] < target) {
        
                left = mid + 1;// 下一个搜索区间为[mid + 1,right]
            } else if (nums[mid] > target) {
        
                right = mid - 1;// 下一个搜索区间为[left,mid - 1]
            }
        }
        return -1;
    }

##### 语法特点 #####

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

##### 算法缺陷 #####

比如 nums = \[1,2,2,2,3\]，target = 2，此算法返回的索引值为 2，虽然返回值没错，但是如果我想得到 target 的左侧边界，即索引值为 1；或者想得到 target 的右侧边界，即索引值为 3。这种情况依靠此算法是无法实现的。

#### 3.2 模板2：搜索区间左闭右开，寻找左侧边界 ####

int binarySearch(int[] nums, int target) {
        
        if (nums == null || nums.length == 0) return -1;
        int left = 0;
        int right = nums.length;// 搜索区间为[left,right)，左闭右开
        while (left < right) {
        // 循环终止条件: left == right，此时搜索区间[left,left)为空，终止循环
            int mid = left + (right - left) / 2;// 防止(left + right)溢出
            if (nums[mid] < target) {
        
                left = mid + 1;// 下一个搜索区间为[mid + 1,right)
            } else if (nums[mid] >= target) {
        
                right = mid;// 下一个搜索区间为[left,mid)
            }
        }
        if (left == nums.length) return -1;// target比所有数都大，返回-1
        return nums[left] == target ? left : -1;// 不存在该值则返回-1
    }

##### 语法特点 #####

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

##### 关键点 #####

*  当`nums[mid] == target`时，并非立即返回，而是缩小搜索区间的上界 right，不断向左收缩
 *  需要后处理，当只剩下一个元素时，需要判断元素是否符合条件

#### 3.3 模板3：搜索区间左闭右开，寻找右侧边界 ####

int binarySearch(int[] nums, int target) {
        
        if (nums == null || nums.length == 0) return -1;
        int left = 0;
        int right = nums.length;// 搜索区间为[left,right)，左闭右开
        while (left < right) {
        // 终止条件: left == right，此时搜索区间[left,left)为空，终止循环
            int mid = left + (right - left) / 2;// 防止(left + right)溢出
            if (nums[mid] <= target) {
        
                left = mid + 1;// 下一个搜索区间为[mid + 1,right)
            } else if (nums[mid] > target) {
        
                right = mid;// 下一个搜索区间为[left,mid)
            }
        }
        if (left == 0) return -1;// target比所有数都小，返回-1
        return nums[left - 1] == target ? (left - 1) : -1;// 不存在该值则返回-1
    }

##### 语法特点 #####

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

##### 关键点 #####

*  当`nums[mid] == target`时，并非立即返回，而是增大搜索区间的下界left，不断向右收缩
 *  需要后处理，当只剩下一个元素时，需要判断元素是否符合条件

### 4 二分查找相关题目（题目来源：Leetcode） ###

#### 4.1 二分查找 ####

##### 4.1.1 题目描述 #####

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

**示例 1**

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

**示例 2**

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

**题目来源**

*  [704. 二分查找 - 力扣（Leetcode）][704. _ - _Leetcode]

##### 4.1.2 解题思路 #####

> 基本的二分查找

##### 4.1.3 Java 代码实现 #####

public int search(int[] nums, int target) {
        
        int left = 0;
        int right = nums.length - 1;
    
        while (left <= right) {
        
            // 等同于 (left + right) / 2，下面的写法可以防止溢出
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
        
                return mid;
            } else if (nums[mid] > target) {
        
                // 收缩右侧边界
                right = mid - 1;
            } else if (nums[mid] < target) {
        
                // 收缩左侧边界
                left = mid + 1;
            }
        }
        return -1;
    }

#### 4.2 搜索插入位置 ####

##### 4.2.1 题目描述 #####

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为`O(log n)`的算法。

**示例 1**

输入: nums = [1,3,5,6], target = 5
    输出: 2

**示例 2**

输入: nums = [1,3,5,6], target = 2
    输出: 1

**示例 3**

输入: nums = [1,3,5,6], target = 7
    输出: 4

**题目来源**

*  [35. 搜索插入位置 - 力扣（Leetcode）][35. _ - _Leetcode]

##### 4.2.2 解题思路 #####

> 基本的二分查找，找不到值不返回-1，返回按顺序插入的索引值

##### 4.2.3 Java 代码实现 #####

public int searchInsert(int[] nums, int target) {
        
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
        
            // 等同于 (left + right) / 2，下面的写法可以防止溢出
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
        
                return mid;
            } else if (nums[mid] < target) {
        
                // 收缩左侧边界
                left = mid + 1;
            } else if (nums[mid] > target) {
        
                // 收缩右侧边界
                right = mid - 1;
            }
        }
        // 目标值不存在数组中，此时下标 left 对应元素为数组中比 target 大的最小值，故按顺序应将目标值插入 left 的位置
        return left;
    }

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

##### 4.3.1 题目描述 #####

给你一个按照非递减顺序排列的整数数组`nums`，和一个目标值`target`。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值`target`，返回`[-1, -1]`。

你必须设计并实现时间复杂度为`O(log n)`的算法解决此问题。

**示例 1**

输入：nums = [5,7,7,8,8,10], target = 8
    输出：[3,4]

**示例 2**

输入：nums = [5,7,7,8,8,10], target = 6
    输出：[-1,-1]

**示例 3**

输入：nums = [], target = 0
    输出：[-1,-1]

**题目来源**

*  [34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（Leetcode）][34. _ - _Leetcode]

##### 4.3.2 解题思路 #####

> 二分查找，分别查出左右边界值，然后组合返回

##### 4.3.3 Java 代码实现 #####

public int[] searchRange(int[] nums, int target) {
        
        if (nums == null || nums.length == 0) {
        
            return new int[]{
        -1, -1};
        }
    
        // 找左侧边界
        int left = 0;
        int right = nums.length;
        while (left < right) {
        
            // 等同于 (left + right) / 2，下面的写法可以防止溢出
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
        
                // 收缩右侧边界，左闭右开区间，不包含下标 right 对应的元素，所以直接将 mid 赋值给 right 即可
                right = mid;
            } else {
        
                // 收缩左侧边界
                left = mid + 1;
            }
        }
        // 后处理，当只剩下一个元素时，需要判断元素是否符合条件
        if (left == nums.length || nums[left] != target) {
        
            // 数组中不存在该值
            return new int[]{
        -1, -1};
        }
        // 数组中存在该值，左侧边界为
        int leftVal = left;
    
        // 找右侧边界
        left = 0;
        right = nums.length;
        while (left < right) {
        
            // 等同于 (left + right) / 2，下面的写法可以防止溢出
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
        
                // 收缩左侧边界
                left = mid + 1;
            } else {
        
                // 收缩右侧边界，左闭右开区间，不包含下标 right 对应的元素，所以直接将 mid 赋值给 right 即可
                right = mid;
            }
        }
        // 不需要后处理，因为前面寻找左侧边界时做过判断了，能走到这里数组中必然存在该值，右侧边界为
        int rightVal = left - 1;
    
        return new int[]{
        leftVal, rightVal};
    }

#### 4.4 x 的平方根 ####

##### 4.4.1 题目描述 #####

给你一个非负整数`x`，计算并返回`x`的**算术平方根**。

由于返回类型是整数，结果只保留**整数部分**，**小数部分**将被舍去。

**注意**：不允许使用任何内置指数函数和运算符，例如`pow(x, 0.5)`或者`x ** 0.5`。

**示例 1**

输入：x = 4
    输出：2

**示例 2**

输入：x = 8
    输出：2
    解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

**题目来源**

*  [69. x 的平方根 - 力扣（Leetcode）][69. x _ - _Leetcode]

##### 4.4.2 解题思路 #####

> 对区间 \[0, x\] 进行二分查找，计算 (long) mid \* mid 与 x 作比较（转为long类型防止 int 类型值相乘后溢出），或者更换成除法操作 x / mid 与 mid 作比较防止溢出（需要排除一些特殊情况，避免除数 mid 为 0 的情况）。
> 
> 注意：由于题干要求保留整数部分，所以 int 类型值相除后自动舍弃小数部分也能满足要求，例如：5 / 2 == 2 在这个逻辑判断里是合法的

##### 4.4.3 Java 代码实现 #####

public int mySqrt(int x) {
        
        // 0或1直接返回，避免后面的除数mid为0
        if (x < 2) {
        
            return x;
        }
        int left = 0;
        int right = x;
        while (left <= right) {
        
            // 等同于 (left + right) / 2，下面的写法可以防止溢出
            int mid = left + (right - left) / 2;
            // 更换成除法操作，防止溢出
            if (x / mid == mid) {
        
                return mid;
            } else if (x / mid > mid) {
        
                // 收缩左侧边界
                left = mid + 1;
            } else {
        
                // 收缩右侧边界
                right = mid - 1;
            }
        }
        // 走到这里说明 x 非完全平方数，此时下标 left 对应元素为数组中比 x 的算数平方根 大的最小整数值
        // 题干要求保留整数部分，舍去小数部分，故应该返回数组中比 x 的算数平方根 小的最大整数值，也就是 left - 1
        // while 循环的终止条件为 left = right + 1，所以 left - 1 等同于 right
        return right;
    }

#### 4.5 有效的完全平方数 ####

##### 4.5.1 题目描述 #####

给你一个正整数`num`。如果`num`是一个完全平方数，则返回`true`，否则返回`false` 。

**完全平方数**是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如`sqrt`。

**示例 1**

输入：num = 16
    输出：true
    解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

**示例 2**

输入：num = 14
    输出：false
    解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

**题目来源**

*  [367. 有效的完全平方数 - 力扣（Leetcode）][367. _ - _Leetcode]

##### 4.5.2 解题思路 #####

> 对区间 \[0, num\] 进行二分查找，计算 mid \* mid 与 num 作比较，相同则返回 true。
> 
> 注意：要将 mid \* mid 的结果转为 long 类型，防止超过 int 类型最大值溢出；另此处不可以使用将 mid \* mid == num 的判断改为除法 num / mid == mid，因为计算参数都是 int 类型，结果会直接舍弃小数部分，造成错误计算，例如：5 / 2 == 2

##### 4.5.3 Java 代码实现 #####

public boolean isPerfectSquare(int num) {
        
        int left = 0;
        int right = num;
        while (left <= right) {
        
            // 等同于 (left + right) / 2，下面的写法可以防止溢出
            int mid = left + (right - left) / 2;
            // 强转为 long 类型，防止 int 值溢出
            long square = (long) mid * mid;
            if (square == num) {
        
                return true;
            }
            if (square < num) {
        
                // 收缩左侧边界
                left = mid + 1;
            } else {
        
                // 收缩右侧边界
                right = mid - 1;
            }
        }
        return false;
    }

[c25c46a47dc84db180bccf544f6106b5.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/a71ae3355ad442459463df80948617e5.png
[704. _ - _Leetcode]: https://leetcode.cn/problems/binary-search/
[35. _ - _Leetcode]: https://leetcode.cn/problems/search-insert-position/
[34. _ - _Leetcode]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
[69. x _ - _Leetcode]: https://leetcode.cn/problems/sqrtx/
[367. _ - _Leetcode]: https://leetcode.cn/problems/valid-perfect-square/