二分算法（java超详细）

青旅半醒 2024-03-31 12:29 32阅读 0赞

#### 文章目录 ####

**目录**

文章目录

一、二分查找

1. 整数二分

1.1 二分查找算法模板1

1.2 二分查找算法模板2

1.3 二分查找算法模板3

1.4 二分查找算法模板4

1.5 二分查找算法模板5

练习题目+详解

2. 浮点数二分

总结

--------------------

## 一、二分查找 ##

### 1. 整数二分 ###

二分查找：也称折半搜索，对数搜索，是用来在一个有序数组中查找某一元素的算法。

例子：在一个升序数组中查找一个数。每次考察数组当前部分的中间元素（middle），如果中间元素刚好是目标元素(target)，就结束搜索。如果中间元素小于所查找的值，就在数组左半部分\[left,middle\]查找；如果中间元素大于所查找的值，就在数组右半部分\[middle,right\]查找。

二分搜索法可以用来查找满足某一条件的最大（最小）值。

要求满足某种条件的最大值最小可能情况（最大值最小化），首先的想法是从小到大枚举这个作为答案的\[最大值\]，然后去判断是否合法。若答案单调，就可以使用二分搜索法来更快的找到答案

使用二分搜索法解决\[最大值最小化\]条件：

1.  答案在一个固定区间内
2.  比较容易判断某个值是否符合条件
3.  可行解对于区间满足一定的单调性（x符合条件，那么x-1或x+1也符合条件）

*  时间复杂度：最优情况O(1)，平均/最坏时间复杂度O(log n)

#### 1.1 二分查找算法模板1 ####

**算法思路**

假设目标值在闭区间`[l,r]`中，每次将区间长度缩小一半，当`l=mid`时，找到目标值

区间`[l,r]`划分为`[l,mid-1]`和`[mid+1,r]`;更新操作为`r=mid-1`或`l=mid+1。`

int binarySearch(int[] nums, int target){
      if(nums == null || nums.length == 0){ //数组为空
        return -1;
      }
      int l = 0, r = nums.length - 1; //设置左右边界
      while(l <= r){ 
        int mid = l + (r-l) / 2; // 等同于mid=(l+r)/2,这种写法是为了防止数组越界,也可以写为(l+r) >>> 1
        if(nums[mid] == target){ //最终target=mid,输出mid
            return mid; 
        }else if(nums[mid] < target) { //目标值在(mid,r]之间
            l = mid + 1; 
        }else {  //目标值在[l,mid)之间
            r = mid - 1; 
        }
      }
      // 最后判断: l>r 即数组不存在
      return -1;
    }

#### 1.2 二分查找算法模板2 ####

**算法思路**

假设目标值在闭区间`[l,r]`中，每次将区间长度缩小一半，当`l=left`时，找到目标值

区间`[l,r]`划分为`[l,mid]`和`[mid+1,r]`;更新操作为`r=mid`或`l=mid+1`(与模板一的区别是界限不同)

int binarySearch(int[] nums, int target){
      if(nums == null || nums.length == 0){ //数组为空
        return -1;
      }
      int l = 0, r = nums.length - 1; //设置左右边界
      while(l <= r){ 
        int mid = l + (r-l) / 2; 
        if(nums[mid] > target) {  //目标值在[l,mid]之间
            r = mid; 
        }else if(nums[mid] < target){
            l = mid+1;
        }else{
            r = mid;
        }
      }
      if(nums[l] == target){
          return l; //当l=left时，找到目标值的下标
      }
      return -1;
    }

#### 1.3 二分查找算法模板3 ####

**算法思路**

假设目标值在闭区间`[l,r]`中，每次将区间长度缩小一半，当`l=right`时，找到目标值

区间`[l,r]`划分为`[l,mid-1]`和`[mid,r]`;更新操作为`r=mid-1`或`l=mid`(与模板一的区别是界限不同)

int binarySearch(int[] nums, int target){
      if(nums == null || nums.length == 0){ //数组为空
        return -1;
      }
      int l = 0, r = nums.length - 1; //设置左右边界
      while(l <= r){ 
        int mid = (l+r+1) / 2; //这种版本会有边界问题，计算mid要加1
        if(nums[mid] > target) {  //目标值在[l,mid]之间
            r = mid-1; 
        }else if(nums[mid] < target){
            l = mid;
        }else{
            r=mid-1;
        }
      }
      if(nums[r] == target){
          return r; //当l=right时，找到目标值的下标
      }
      return -1;
    }

#### 1.4 二分查找算法模板4 ####

**关于开闭区间问题**

二分查找 \[left, right)

*  用于查找需要访问**数组中当前索引及其直接右邻居索引**的元素或条件。
 *  使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
 *  保证查找空间在每一步中至少有 2 个元素。
 *  需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

// 二分查找 [left, right)
        int binarySearch2(int[] nums, int target){
            if(nums == null || nums.length == 0)
                return -1;
            // 定义target在左闭右开的区间里，即：[left, right)
            int left = 0, right = nums.length;
            // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            while(left < right){
                int mid = left + (right - left) / 2;
                if(nums[mid] == target){
                    return mid;
                }
                else if(nums[mid] < target) {
                    //  target 在右区间，在[mid + 1, right)中
                    left = mid + 1;
                }
                else {
                    // target 在左区间，在[left, middle)中
                    right = mid;
                }
            }
            //当 left == right
            if(left != nums.length && nums[left] == target) return left;
            return -1;
        }

#### 1.5 二分查找算法模板5 ####

二分查找 (left, right)

搜索需要**访问当前索引及其在数组中的直接左右邻居索引**的元素或条件。

*  搜索条件需要访问元素的直接左右邻居。
 *  使用元素的邻居来确定它是向右还是向左。
 *  保证查找空间在每个步骤中至少有 3 个元素。
 *  需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。

// 二分查找 (left, right)
        int binarySearch3(int[] nums, int target) {
            if (nums == null || nums.length == 0)
                return -1;
    
            int left = 0, right = nums.length - 1;
            while (left + 1 < right){
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) {
                    return mid;
                } else if (nums[mid] < target) {
                    //  target 在右区间，在(middle, right)中
                    left = mid;
                } else {
                    // target 在左区间，在(left, middle)中
                    right = mid;
                }
            }
            // 当: left + 1 == right
            if(nums[left] == target) return left;
            if(nums[right] == target) return right;
            return -1;
        }

**关于模板中出现的边界问题**

更新之后的mid仍然为L，左右边界没有发生变化，会使while陷入死循环，所以求mid=(r+l+1)/2

![c3aaaafc71184cf7b2b882c0fe1a137a.png][]

####  ####

#### 练习题目+详解 ####

**练习题1**

![6db710b9907e4f2cb6900b116ccd15ff.png][]

**思路**

思路也很简单，就是用二分法找到每一个数字的下标，这里要注意，我们需要找到每个元素第一次出现的位置，所以需要设置`l<r`，然后递归的时候`r=mid`, 这样如果目标值存在的话，就返回`l`的位置。

**代码**

public class 二分查找 {
        static int a[] = new int[10^6+10]; //定义一个数组a的全局变量
        static int binarySearch(int x, int n) { //x是目标值，n是数组长度
            int l = 0; int r = n-1 ;
            while (l<r){
                int mid = (l+r)/2;
                if(a[mid] < x) l = mid+1;
                else r = mid;
                
            }
            //找到目标值，返回下标
            if(a[l] == x) return l+1; //注意：从1开始编号
            else return -1;
    
        }
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            //用户输入n,m 分别代表数组长度,询问次数
            int n = sc.nextInt(), m = sc.nextInt();
            //这里读入数组
            for(int i = 0; i < n; i++){
                a[i] = sc.nextInt();
            }
    
            //挨个找数字的下标
            for(int i = 0; i < m; i++){
                int q = sc.nextInt();
                int ans = binarySearch(q, n);
                System.out.print(ans + " ");
            }
        }
    }

**练习题2**

> 给你一个按照非递减顺序排列的整数数组 `nums`，和一个目标值 `target`。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 `target`，返回 `[-1, -1]`。你必须设计并实现时间复杂度为 `O(log n)` 的算法解决此问题。

**思路**

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 target 的下标，但这个方法的时间复杂度为 O(n)，没有利用到数组升序排列的条件。由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

考虑 target 开始和结束位置，其实我们要找的就是数组中「第一个等于 target 的位置」（记为 left）和「第一个大于 target 的位置减一」（记为 right）。

二分查找中，寻找 left 即为在数组中寻找第一个**等于** target 的下标，寻找 right 即为在数组中寻找第一个**大于** target 的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义 searchRange(nums,target) 表示在 nums数组中二分查找 target 的位置 。

最后，因为 target可能不存在数组中，因此我们需要重新校验我们得到的两个下标 left 和 right，看是否符合条件，不符合就返回 \-1,-1。

public class 查找下标 {
    
        public int[] searchRange(int[] nums, int target){
            int len = nums.length;
            if(len == 0){
                return new int[]{-1,-1};
            }
    
            int firstPosition = findFirstPosition(nums,target);
            if(firstPosition == -1){
                return new int[]{-1,-1};
            }
    
            int lastPositon = findLastPosition(nums,target);
            return new int[]{firstPosition,lastPositon};
        }
    
        private int findFirstPosition(int[] nums, int target){
    
            int left = 0;
            int right = nums.length-1;
            while(left < right){ //这里没有包含left=right的情况
                int mid = (left+right)/2;
                if(nums[mid] < target){
                    //在[mid+1,right]之间找
                    left = mid+1;
                }else if(nums[mid] > target){
                    //在[ledt,mid-1]之间找
                    right = mid-1;
                }else{
                    //在[left,mid]之间找
                    right = mid;
                }
            }
            if(nums[left] == target){
                return left;
            }
            return -1;
        }
    
        private int findLastPosition(int[] nums, int target){
    
            int left = 0;
            int right = nums.length-1;
            while(left < right){ //这里没有包含left=right的情况
                int mid = (left+right+1)/2;
                if(nums[mid] < target){
                    //在[mid+1,right]之间找
                    left = mid+1;
                }else if(nums[mid] > target){
                    //在[ledt,mid-1]之间找
                    right = mid-1;
                }else{
                    //在[mid，right]之间找
                    left = mid;
                }
            }
            return left;
        }
    }

*  >>表示右移，如果该数为正，则高位补0，若为负数，则高位补1；
 *  >>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0。
 *  时间复杂度：O*（log n）*

**练习题3**

> 整数数组 `nums` 按升序排列，数组中的值 **互不相同** 。
> 
> 在传递给函数之前，`nums` 在预先未知的某个下标 `k`（`0 <= k < nums.length`）上进行了 **旋转**，使数组变为 `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`（下标 **从 0 开始** 计数）。例如， `[0,1,2,4,5,6,7]` 在下标 `3` 处经旋转后可能变为 `[4,5,6,7,0,1,2]` 。给你 **旋转后** 的数组 `nums` 和一个整数 `target` ，如果 `nums` 中存在这个目标值 `target` ，则返回它的下标，否则返回 `-1` 。
> 
> 你必须设计一个时间复杂度为 `O(log n)` 的算法解决此问题。

**思路**

这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 \[4, 5, 6\] 和 \[7, 0, 1, 2\] 两个部分，其中左边 \[4, 5, 6\] 这个部分的数组是有序的，其他也是如此。这启示我们可以在常规二分查找的时候查看当前 `mid` 为分割位置分割出来的两个部分 `[l, mid]` 和 `[mid + 1, r]` 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 `target` 在不在这个部分：

*  如果 `[l, mid - 1]` 是有序数组，且 target 的大小满足`[nums[l],nums[mid]`，则我们应该将搜索范围缩小至 `[l, mid - 1]`，否则在 `[mid + 1, r]` 中寻找。
 *  如果 `[mid, r]` 是有序数组，且 target 的大小满足 `[nums[mid+1],nums[r]]`，则我们应该将搜索范围缩小至 `[mid + 1, r]`，否则在 `[l, mid - 1]` 中寻找。

需要注意的是，二分的写法有很多种，所以在判断 target 大小与有序部分的关系的时候可能会出现细节上的差别。

public class 螺旋数组 {
        public int search(int[] nums, int target) {
            int n = nums.length;
            if (n == 0) {
                return -1;
            }
            if (n == 1) {
                return nums[0] == target ? 0 : -1;
            }
            int l = 0, r = n - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] == target) {
                    return mid;
                }
                if (nums[0] <= nums[mid]) { //如果左边是有序的
                    if (nums[0] <= target && target < nums[mid]) {//目标值在左边
                        r = mid - 1;
                    } else { //如果目标值在右边
                        l = mid + 1;
                    }
                } else { //如果左边是无序的，就相当于遍历该区间元素了
                    if (nums[mid] < target && target <= nums[n - 1]) {//目标值在右边
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
            }
            return -1;
        }
    }

**复杂度分析**

*  时间复杂度： O(log⁡n)，其中 n 为nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(logn)。
 *  空间复杂度： O(1) 。我们只需要常数级别的空间存放变量。

### 2. 浮点数二分 ###

浮点数二分：将整数二分中的mid的类型替换成double，将区间更新操作改为l=mid或r=mid，当区间长度足够小（能求出答案时），就可以结束二分。注：浮点数二分不存在边界问题。

代码示例

double binarySearch(int[] nums,int target){
    	// eps 表示精度，取决于题目对精度的要求
        double l = 0; double r = nums.length-1;
        const double eps = 1e-6; //科学计数法1*10^-6 当区间长度小于eps时退出循环 
        while (r - l > eps){ //当区间长度大于eps时继续二分
            double mid = (l + r) / 2;
            if (nums[mid] > target ) r = mid;
            else l = mid;
        }
        return l; //最后while循环退出的时候l和r近似相等
    }

--------------------

## 总结 ##

这里对文章进行总结：  
以上就是整理的二分算法的内容，本文仅仅简单介绍了二分算法，而要在具体的题目中真正掌握运用二分算法，还需要多加练习二分算法的各种题目。

[c3aaaafc71184cf7b2b882c0fe1a137a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e138f492265442f08c483880d2c6d001.png
[6db710b9907e4f2cb6900b116ccd15ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1da35efd48314363bbb36815f2c8f6ac.png