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

MicroFrank

发布于 2023-04-12 09:37:01

8610

发布于 2023-04-12 09:37:01

文章被收录于专栏：同步文章1234

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

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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-04-09，如有侵权请联系 cloudcommunity@tencent.com 删除

target