剑指offer53:在排序数组中查找数字

剑指offer53:在排序数组中查找数字

目录

1.暴力

2.二分

---

1.暴力

找到数字遍历到下一个结束位置然后求出长度

2.二分

数组是排序的嘛毕竟~，想必很多人都知道怎么写，总体思路也是求左右区间然后求长度：

class Solution {
public:
    int binarySearch(vector& nums, int target, bool lower) {
        int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    int search(vector& nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx) {
            //&& rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target
            return rightIdx - leftIdx + 1;
        }
        return 0;
    }
};

但是每次，二分查找中的边界问题总是让人头大呢。

这里有些细节：

用low实现了求区间点的合并。

这个ans的设置，可以举一个[1]来试试，但是为什么这样设置我也不大懂。。。

说实话offer中拆开的函数感觉理解起来更人性化。具体可以见原书p263

当然，书中的《0~n-1中缺失的数字》和《数组中数值和下标相等的元素》两个例子我觉得对于理解二分也很友好，感兴趣的同学可以康康~

0~n-1中确实的数字：

 聪明的你是不是马上想到，这个数组里面有两组性质的数据，一类是数组下标和下标对应值相等的，可以称之为左半区，右半区是什么呢，是下标比下标对应数小1的，利用这个性质，我们可以进行二分：

class Solution {
public:
    int missingNumber(vector& nums) {
        int left=0,right=nums.size()-1;
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]==mid)
            {
                left=mid+1;
            }
            else
            {
                if(mid==0 || (mid>0&&nums[mid-1]==mid-1))
                {
                    return mid;
                }
                right=mid-1;
            }
        }
        if(left==nums.size()) return left;
        return -1;
    }
};

当然，这里面有点细节，可能有的小伙伴不知道为什么循环出来还要判断一下left和数组大小的关系，可以看看这个例子：

 是不是有感觉了？没错，如果没有在循环出来判断的话，我们会漏掉一种情况，也就是这个数组中全是左半区，没有右半区。。。。。。然后用例子分析一下二分的代码，可以发现在这种情况下left会指向数组末尾后一位，也就是正好是我们要返回的那个值。。。。。。

结果如下：