剑指offer在排序数组中的二分法应用总结

ゞ浴缸里的玫瑰 2024-03-26 19:23 52阅读 0赞

##  ##

**排序数组中的搜索问题，首先想到 二分法 解决，本篇详细解析关于二分法边界的问题。**

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

**目录**

一、二分法概念

二、剑指Offer53.在排序数组中查找数字

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

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

**一、二分法概念**

> 二分法就是在一个有序递增的数组中进行折半查找。
> 
> 如果中间的数字**大于**目标值，则**right = middle - 1**，全部排除
> 
> 如果中间的数字**小于**目标值，则**left = middle + 1**，全部排除

普通写法：

int search(int nums[], int size, int target) //nums是数组，size是数组的大小，target是需要查找的值
    {
        int left = 0;
        int right = size - 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 {	//既不在左边，也不在右边，那就是找到答案了
                return middle;
            }
        }
        //没有找到目标值
        return -1;
    }

> 循环条件要使用while(left<=right)因为当`(left == right)`这种情况发生的时候，得到的结果是有意义的,切记千万不要写成left<right，会找不到target，直接跳出循环。

## **二、剑指Offer53.在排序数组中查找数字** ##

### `` ###

> [剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode）][Offer 53 - I. _ I - _LeetCode]
> 
> 统计一个数字在排序数组中出现的次数。
> 
> ![28ec1474c1c14cff8cecfd9733841fbd.png][]

> 思路：在排序数组中的所有数字形成一个窗口，记录左边界和右边界，由于数组 nums 中元素都为整数，因此可以分别二分查找 target 和 target−1 的右边界，将两结果相减并返回即可。

class Solution {
        public int search(int[] nums, int target) {
            return helper(nums,target)-helper(nums, target-1);
        }
        public int helper(int[] nums,int target){
            int i = 0,j = nums.length-1;
            while (i <= j){
                int m = (i+j) / 2;
                if (nums[m] <= target){
                    i = m+1;
                }else {
                    j = m-1;
                }
            }
            return i;
        }
    }

![ee07862161f040ef898ff69d230b0f0d.png][]

> 在寻找边界的过程中，如果将if(nums\[m\] < target)就变成了求左边界。

public int helper2(int[] nums,int target){
            int i = 0,j = nums.length-1;
            while (i <= j){
                int m = (i+j) / 2;
                if (nums[m] < target){
                    i = m+1;
                }else {
                    j = m-1;
                }
            }
            return j;
        }

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

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

![924b713762644cd6b5b5ef6e73f3306c.png][]

>  思路：分别找到target的右边界和target-1的右边界，然后将target-1的边界-1放进int\[\]数组中输出，随后return

class Solution {
        public int[] searchRange(int[] nums, int target) {
            int[] res = new int[] {-1, -1};
            
            int a = helper(nums,target-1);
            int b = helper(nums,target);
            if(b - a > 0){
                return new int[]{a,b-1};
            }
            return res;
        }
        int helper(int[] nums,int target){
            int i = 0,j = nums.length-1;
            while (i <= j){
                int m = i + (j-i) / 2;
                if (nums[m] <= target){
                    i = m+1;
                }else {
                    j = m-1;
                }
            }
            return i;
        }
    }

分享一下心酸历史：![b33a14b3c368440dae86a0279ba413f3.png][]

[Offer 53 - I. _ I - _LeetCode]: https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
[28ec1474c1c14cff8cecfd9733841fbd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/0776bf4377794c84b46901963ebd9755.png
[ee07862161f040ef898ff69d230b0f0d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/75f7a6fe6e2d41e4a89a861a9add3384.png
[34. _ _ - _LeetCode]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/
[924b713762644cd6b5b5ef6e73f3306c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/7e12203d3cd44a218b4d92e6dfab1b3f.png
[b33a14b3c368440dae86a0279ba413f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/44f293067cf945f9a772473495b2dce4.png