二分查找专题

向右看齐 2023-06-13 06:07 108阅读 0赞

# 二分查找专题 #

### 文章目录 ###

*  二分查找专题
 *   *  一，简单的二分查找
     *   *  二分查找
         *  二分边界查找
         *   *  寻找左侧边界的二分搜索
             *  寻找右侧边界的二分搜索
     *  二，有序数组中使用二分搜索
     *   *  搜索插入位置
         *  在排序数组中查找元素的第一个出现和最后一个出现的位置
     *  三，旋转数组
     *   *  搜索旋转排序数组
         *  搜索旋转排序数组II
         *  寻找旋转排序数组中的最小值
         *  寻找旋转排序数组中的最小值II
     *  四，其他
     *   *  求平方
         *  第一个错误版本

## 一，简单的二分查找 ##

二分查找也叫作折半查找，是一种效率较高的查找方法，前提是数据结构必须先排好序，可以在数据规模的对数时间复杂度内完成查找，但是，二分查找要求线性表具有随机访问的特点（数组）也要求线性表能根据中间元素推断出它两侧元素的性质（事先排好序），以达到缩减问题规模的效果

### 二分查找 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]

在查找中间元素的时候推荐使用：(可防止越界)，在后面的实现中，我还是使用的是 mid = (left + right) / 2，因为这是之前做的题，现在是想总结一下，就没改过来

int left = 0;
    int right = nums.length - 1;
    int mid = left + (right - left) / 2;

实现

public int search(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            int mid;
            while(left <= right){
        
                mid = (left + right) / 2;
                //找到了目标元素
                if(nums[mid] == target){
        
                    return mid;
                }else if(nums[mid] > target){
        
                    //目标元素在左侧
                    right = mid - 1;
                }else{
        
                     //目标元素在右侧
                    left = mid + 1;
                }
                //缩小区间，继续循环查找
            }
            //没有找到则返回-1，此时left > right,查找区间中没有要查的元素
            return -1;
        }

### 二分边界查找 ###

二分边界查找一般适用于：

*  有序数组，数组元素有重复
 *  循环数组，数组部分有序，数组元素可能重复，可能不重复

#### 寻找左侧边界的二分搜索 ####

刚刚也提到过，边界查找适用于有重复元素的序列，比如：

1 2 2 2 3 4 5 6 6 ，target = 2

那么2的边界值（索引）就是

*  最左边界值：1
 *  最右边界值：3

> 思想其实就一句话概括

左侧边界的二分搜索就是不断向左收缩

/**
         * 寻找左侧边界的二分搜索
         * @param nums
         * @param target
         * @return
         */
        public int searchLeft(int[] nums,int target){
        
            int left = 0;
            int right = nums.length;
            //搜索区间：[left，right)，不能搜索到right，right会越界
            while(left < right){
        
                int mid = (left + right) / 2;
                if(nums[mid] == target){
        
                    //继续向左收缩
                    right = mid;
                }else if(nums[mid] > target){
        
                    //target在左边，为什么right = mid 而不是 mid - 1呢，因为，这里right 取值为 nums.length，
                    right = mid;
                }else{
        
                    //target在右边
                    left = mid + 1;
                }
            }
            return left;
        }

#### 寻找右侧边界的二分搜索 ####

> 道理是一样的，但是实现上有些许不同

右侧边界的二分搜索就是不断向右收缩

/**
         * 寻找右侧边界的二分查找
         * @param nums
         * @param target
         * @return
         */
        public int searchRight(int[] nums,int target){
        
            int left = 0;
            int right = nums.length;
            //搜索区间：[left，right)，不能搜索到right，right会越界
            while(left < right){
        
                int mid = (left + right) / 2;
                if(nums[mid] == target){
        
                    //找到目标值；继续向右收缩
                    left = mid + 1;	//###第一处不同
                }else if(nums[mid] > target){
        
                    //target在左侧，收紧
                    right = mid;
                }else{
        
                    //target在右侧，收紧
                    left = mid + 1;//###第二处不同
                }
            }
            //因为收紧左侧边界时（nums[mid] = target）必须 left = mid + 1
            //所以最后无论返回 left 还是 right，必须减一
            return left - 1;//###第三处不同
        }

## 二，有序数组中使用二分搜索 ##

> 刚刚看了二分查找的基本定义和一些基本的实现模板，现在看看具体的一些题目

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]

这个其实跟普通简单二分没有什么区别

public int searchInsert(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            int mid;
            while(left <= right){
        
                mid = (left + right) / 2;
                if (nums[mid] == target){
        
                    return mid;
                }else if(nums[mid] > target){
        
                    right = mid - 1;
                }else{
        
                    left = mid + 1;
                }
            }
            return left;
        }

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]

这道题目其实就是相当于找出target在这个有序且升序数组中的左边界和有边界

public int[] searchRange(int[] nums, int target) {
        
    //线性扫描法 O(N)
    //        if(nums.length == 0 ||target < nums[0] || target > nums[nums.length - 1]){
        
    //            return new int[]{-1,-1};
    //        }
    //        ArrayList<Integer> list = new ArrayList<>();
    //        for(int i = 0;i < nums.length;i++){
        
    //            if(nums[i] == target){
        
    //                list.add(i);
    //            }
    //        }
    //        return list.size() == 0 ? new int[]{-1,-1}:new int[]{list.get(0),list.get(list.size()-1)};
            
    //---------------- 二分法 ------------------------------
            if(nums.length == 0 ||target < nums[0] || target > nums[nums.length - 1]){
        
                return new int[]{
        -1,-1};
            }
            int left = searchLeft(nums, target) ;
            if(nums[left] != target || left == nums.length){
        
                return new int[]{
        -1,-1};
            }
            int right = searchRight(nums, target);
            if(right == nums.length || nums[right] != target){
        
                return new int[]{
        -1,-1};
            }
            return new int[]{
        left,right};
        }
    
        /**
         * 寻找左侧边界的二分搜索
         * @param nums
         * @param target
         * @return
         */
        public int searchLeft(int[] nums,int target){
        
            int left = 0;
            int right = nums.length;
            //搜索区间：[left，right)，不能搜索到right，right会越界
            while(left < right){
        
                int mid = (left + right) / 2;
                if(nums[mid] == target){
        
                    //向左收缩
                    right = mid;
                }else if(nums[mid] > target){
        
                    //target在左边
                    right = mid;
                }else{
        
                    //target在右边
                    left = mid + 1;
                }
            }
            return left;
        }
    
        /**
         * 寻找右侧边界的二分查找
         * @param nums
         * @param target
         * @return
         */
        public int searchRight(int[] nums,int target){
        
            int left = 0;
            int right = nums.length;
            //搜索区间：[left，right)，不能搜索到right，right会越界
            while(left < right){
        
                int mid = (left + right) / 2;
                if(nums[mid] == target){
        
                    //找到目标值；继续向右收缩
                    left = mid + 1;
                }else if(nums[mid] > target){
        
                    //target在左侧，收紧
                    right = mid;
                }else{
        
                    //target在右侧，收紧
                    left = mid + 1;
                }
            }
            //因为收紧左侧边界时必须 left = mid + 1
            //所以最后无论返回 left 还是 right，必须减一
            return left - 1;
        }

## 三，旋转数组 ##

> 何为旋转数组？

旋转数组其实就是循环数组，比如：

1 2 3 4 5

其实等价于

5 1 2 3 4

因为是头尾相接的，所以相等

> 对于处理这类问题，我们需要找到旋转数组中的变化点，何为变化点，比如：

5 1 2 3 4

对于上边这个数组，原本旋转数组是应该是从左到右是有序的，但是因为是旋转的特点，所以就有可能出现部分有序的现象，比如上边的数组，5之后的1开始就是升序的部分有序序列，所以，1便是这个数组的变化点，变化点索引为1，变化点左右两边的数的特点如下：

nums[left] > nums[change] < nums[right]

判断变化点位置：

int left = 0;
    int right = nums.length;
    int mid = (left + right) / 2;
    if nums[left] < nums[right]	---> 数组没有选择，从左到右皆为有序
    if nums[left] <= nums[mid]  ---> 数组前半部分有序，变化点在后半部分
    else 					  ---> 数组后半部分有序，变化点在前半部分

或者这样也可以：

int left = 0;
    int right = nums.length;
    int mid = (left + right) / 2;
    if nums[mid] > nums[right]	---> 正常来说，有序旋转数组的nums[mid]不可能大于nums[right]，出现这样是因为在区间[mid,right]有变化点

找出了变化点，我们也可以找出了整个旋转数组的最小值所在的索引

> 但是上面提到的一般是没有重复元素的旋转数组，那么有重复元素时，该如何处理呢？

比如：

1 1 1 1 2 2 2 1 1 1 1 1	1 1 1 1 	target = 2

此时我们就分不出是前面有序，还是后半部分有序了，就有可能出现

nums[left] = nums[mid]
    或者
    nums[mid] = nums[right]

所以，当出现这种现象，我们可以收缩区间

if(nums[left] == nums[mid]){
        
                    left = left + 1;
                    continue;
                }
    		   或者
                if(nums[mid] == nums[right]){
        
                    right = right - 1;
                }

### 搜索旋转排序数组 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]

实现

/**
         * 搜索旋转排序数组
         * @param nums
         * @param target
         * @return
         */
        public int search(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            int mid;
            while(left <= right){
        
                mid = (left + right) / 2;
                //找到即返回索引
                if(target == nums[mid]){
        
                    return mid;
                }
                if(nums[left] <= nums[mid]){
        
                    //前半部分有序
                    if(nums[left] <= target && target < nums[mid]){
        
                        // target在区间[left，mid)
                        right = mid - 1;
                    }else{
        
                        // target在区间[mid,right]
                        left = mid + 1;
                    }
                }else{
        
                    //后半部分有序
                    if(nums[mid] < target && target <= nums[right]){
        
                        // target在区间[mid,right]
                        left = mid + 1;
                    }else{
        
                        // target在区间[left，mid)
                        right = mid - 1;
                    }
                }
            }
            return -1;
        }

### 搜索旋转排序数组II ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]

> 与上题区别在于存在重复值

public boolean search11(int[] nums, int target) {
        
    //        for(int i : nums){
        
    //            if(i == target){
        
    //                return true;
    //            }
    //        }
    //        return false;
            int left = 0;
            int right = nums.length - 1;
            int mid;
            while(left <= right){
        
                mid = (left + right) / 2;
                //找到直接返回
                if(target == nums[mid]){
        
                    return true;
                }
                //比如极端情况：11111222111111111 target = 2，此时我们就分不出是前面有序，还是后半部分有序了
                if(nums[left] == nums[mid]){
        
                    left = left + 1;
                    continue;
                }
                if(nums[left] < nums[mid]){
        
                    //前半部分有序
                    if(nums[left] <= target && target < nums[mid]){
        
                        right = mid - 1;
                    }else{
        
                        left = mid + 1;
                    }
                }else{
        
                    if(nums[mid] < target && target <= nums[right]){
        
                        left = mid + 1;
                    }else{
        
                        right = mid - 1;
                    }
                }
            }
            return false;
        }

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 5]

找出变化点即可

/**
         * 在旋转数组中找最小值
         * @param nums
         * @return
         */
        public int findMin(int[] nums) {
        
    //        Arrays.sort(nums);
    //        return nums[0];
            int left = 0;
            int right = nums.length - 1;
            while(left <= right){
        
                int mid = (left + right) / 2;
                if(nums[mid] > nums[right]){
        
                    //如果 nums[mid] > nums[right]:则变换点在[mid，right]区间中
                    //比如：2 3 4 5 1这种情况变换点就是1，为什么要找变换点？
                    //又比如： 4 5 1 2 3, 变换点是1.根据有序旋转特性可知，变换点左右两侧都大于变换点
                    left = mid + 1;
                }else{
        
                    //变化点在[left,mid]
                    right = mid - 1;
                }
            }
            return nums[left];
        }

### 寻找旋转排序数组中的最小值II ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 6]

> 这题和上一道的区别就是该数组元素存在重复

/**
         * 搜索排序数组中的最小值II
         * @param nums
         * @return
         */
        public int findMin(int[] nums) {
        
            int left = 0;
            int right = nums.length - 1;
            while(left <= right){
        
                int mid = (left + right) / 2;
                if(nums[mid] > nums[right]){
        
                    //变化点在右侧
                    left = mid + 1;
                }else if(nums[mid] < nums[right]){
        
                    //变化点在左侧
                    right = mid - 1;
                }else{
        
                    //出现重复现象
                    //此时，nums[mid] = nums[right],需要收缩区间，而right - 1 这种做法不会导致数组越界
                    right = right - 1;
                }
            }
            return nums[left];
        }

## 四，其他 ##

### 求平方 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 7]

一开始我很快就想到这么做

public double myPow(double x, int n) {
        
         return Math.pow(x,n);
    }

其实这道题目的经典解法是二分法：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 8]

public double myPow(double x, int n) {
        
            if(n < 0){
        
                x = 1/x;
                n = -n;
            }
            return fastPow(x,n);
        }
    
        private double fastPow(double x, int n) {
        
            if(n == 0){
        
                return 1.0;
            }
            double half = fastPow(x,n / 2);
            if(n % 2 != 0){
        
                return half * half * x;
            }else{
        
                return half * half;
            }
        }

### 第一个错误版本 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 9]

利用二分法，出错的后边都不能运行，所以，一旦方法在mid找到出错，即mid后的都不行，需要钱left方向收缩

public int firstBadVersion(int n) {
        
        int left = 1;
        int right = n;
        while (left < right) {
        
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
        
                right = mid;
            } else {
        
                left = mid + 1;
            }
        }
        return left;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191113231800819.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191114000140704.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191113233944973.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191114000329491.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191114000812770.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191114001156620.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191114002259360.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2019111414033123.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20191114141836160.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/2019111414212343.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70