【剑指offer|5.在排序数组中查找数字I】

一时失言乱红尘 2024-03-24 17:08 28阅读 0赞

## 0.在排序数组中查找数字I ##

![image-20230409165107001][]

## 1.低效率方法© ##

>  *  通过二分查找找到目标值, 局部时间复杂度O(logN); 然后在目标值左右扫描, 直到分别扫描到第一个3和最后一个3, 因为要查找的数字在长度为N的数组中可能出现N次， 所以局部时间复杂度O(N);
>  *  总体时间复杂度O(N)，效率很低，和直接遍历扫描数个数的笨方法时间复杂度相同O(N)，不可取

int BinarySearch(int* nums, int numsSize, int target)
    {
        
        int left = 0, right = numsSize - 1;
        while (left <= right)
        {
        
            int mid = left + (right - left) / 2;
            if (nums[mid] > target)
            {
        
                right = mid - 1;
            }
            else if (nums[mid] < target)
            {
        
                left = mid + 1;
            }
            else
            {
        
                return mid;
            }
        }
        return -1;
    }
    
    int search(int* nums, int numsSize, int target) {
        
        int count = 0;
        int index = BinarySearch(nums, numsSize, target);
        if (index == -1)
        {
        
            return count;
        }
        else
        {
        
            count++;
        }
            int left=index-1,right=index+1;
            while (left >= 0&&nums[left] == target)
            {
        
                count++;
                left--;    
            }
            while (right < numsSize&&nums[right] == target)
            {
        
                count++;
                right++;
            }
    
        return count;
    }

## 2.二分查找© ##

> 我们考虑怎样更好地利用二分查找，在前面的算法中，时间主要消耗在一个一个找target，从而找到第一个target和最后一个target上，所以我们能不能用通过某种方式更快地直接找到第一个target和最后一个target。
> 
>  *  二分查找算法总是先拿数组中间的数和target作比较，如果中间的数字比target大，则target有可能出现在前半段，下一轮我们只用在前半段找就可以了；如果中间的数字比target小，则target有可能出现在后半段,下一轮我们只用在后半段找就可以了。
>  *  如果中间的数字和target相等那？我们先判断这个数字是不是第一个target，如果这个数字的前一个数字不等于target, 那么这个数字刚好就是第一个target ； 如果这个数字的前一个数字等于target, 那么第一个target一定就在前半段，下一轮我们只用在前半段找就可以了。
>  *  时间复杂度:O(logN)

int GetFirstOfK(int* nums, int numsSize, int target)
    {
        int left = 0, right = numsSize - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target)
            {
                right = mid - 1;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                if (mid-1>=0&&nums[mid - 1] != target || mid==0)//关键边界处理
                {
                    return mid;
                }
                else
                {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
    
    int GetLastOfK(int* nums, int numsSize, int target)
    {
        int left = 0, right = numsSize - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target)
            {
                right = mid - 1;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                if (mid + 1 <numsSize && nums[mid + 1] != target||mid==numsSize-1)
                {
                    return mid;
                }
                else
                {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
    
    int search(int* nums, int numsSize, int target) {
        int count = 0;
        int first = GetFirstOfK(nums, numsSize, target);
        int last = GetLastOfK(nums, numsSize, target);
        if (first != -1 && last != -1)
        {
            return last - first + 1;
        }
        return count;
    }

[image-20230409165107001]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/7fc7ceaaeb8a4670bb1e6cfd539e0946.png