【牛客-算法】 NC48 在旋转过的有序数组中寻找目标值

1.题目描述

描述

有一个长度为 n 的按严格升序排列的整数数组 nums ，在实行 search 函数之前，在某个下标 k 上进行旋转，使数组变为

给定旋转后的数组 nums 和一个整型 target ，请你查找 target 是否存在于 nums 数组中并返回其下标（从0开始计数），如果不存在请返回-1。

数据范围：0 ≤ n ≤ 10000 , 0 ≤ t a r g e t ≤ 100000 0 \le n \le 10000,0 \le target \le 1000000≤n≤10000,0≤target≤100000

要求：空间复杂度 O ( 1 ) O(1)O(1) ，时间复杂度 O ( n ) O(n)O(n)

例子，数组 [ 0 , 2 , 4 , 6 , 8 , 10 ] [0,2,4,6,8,10][0,2,4,6,8,10] 在下标3处旋转之后变为 [ 6 , 8 , 10 , 0 , 2 , 4 ] [6,8,10,0,2,4][6,8,10,0,2,4] , 当给定target为10时，10的下标是2，target为3时，nums数组中不存在3，所以返回-1

2.算法设计思路

前面铺垫那么多干嘛呢？我要做的不就是在数组中遍历搜索一个整数吗？

C代码：一次遍历，

int search(int* nums, int numsLen, int target ) {
    // write code here
    for(int i = 0; i < numsLen; i++)
    {
        if(nums[i] == target)
        {
            return i;
        }
    }
    return -1;
}

后面仔细看了题目和别人的讨论才发现，有一个重要的条件是数组在旋转之前是严格升序的。所有题目的意思是，为了将时间复杂度从 O ( n ) O(n)O(n) 减小为 O ( l o g ( n ) ) O(log(n))O(log(n)) O ( l o g ( n ) ) \Omicron(log(n))O(log(n))，可以采用二分的办法。那么问题来了，在旋转之后，数组就不是严格有序了，要怎么二分呢？

旋转前的数组（左）和旋转后的数组（右） ：

我们仍然取数组的中点 mid，将数组划分为 (left, mid-1) 和 (mid+1, right) 两部分，而其中一定有一个区间是完全有序的（可通过比较端点值来判断）。所以，我们可以将区间分为左、右两个部分分别进行搜索。

（注：下面的 搜索 字眼，若无特别说明，则是指对 不完全有序区间 的搜索）

算法过程：

如果搜索的区间有序

判断 target 是否在该区间中（通过比较端点值）

若在，则对该区间进行完全有序情况下的二分搜索即可（不再赘述）

若不在，则放弃该区间，搜索另一半无序的区间

若搜索的区间不完全有序

再次将该区间划分分为左、右两个部分进行搜索

3.算法实现

bug记录

报错：solution.c:94:13: warning: implicit declaration of function 'serchSorted' is invalid in C99 [-Wimplicit-function-declaration]

翻译过来就是：解决方案.c：94：13： 警告：函数“serch排序”的隐式声明在 C99 中无效 [-微缩-函数-声明]

一看到C99，我还以为是版本的问题，结果实际是代码中拼写错误导致的。我把searchSorted写成了serchSorted，掉了个字母 a。

遇到问题（可跳过）

对一个有序的区间二分的时候，我们要严格的判断目标值 target 在不在区间里，就要用 target 与区间的两个端点都进行比较。而进行过比较的端点，就可以排除出我们接下来要搜索的区间（如果值相等，那就直接找到目标了）。

或者，我们也可以只与区间的中间点这一个端点比较，判断 target 是在区间的哪一边。

哪种方式更好呢？

写在前面

下面的代码显得很长，因为我将搜索有序区间和搜索非有序区间作为两个函数分开来写了。

其实我更推荐你看这篇题解中的 C++ 代码，二十来行解决问题：NC48 在旋转过的有序数组中寻找目标值。

总结一下他的思路：（采用迭代写法，主要是将有序和无序的情况统一起来了）

将区间划分为左、右两部分小区间

找到有序的区间

若该有序区间包含 target：将该区间设为新的目标区间

若不包含 target：将另一半区间设为新的搜索区间

直到找到 target，或区间为空，停止搜索

我最初的通过代码（C语言）

int searchNo(int* nums, int left, int right, int target);

int searchSorted(int *nums, int left, int right, int target);

//调用者函数
int search(int* nums, int numsLen, int target ) {
    // write code here
    int mid = numsLen / 2;
    int x = -1;//注意不是初始化为 0
    x = searchNo(nums, 0, numsLen-1, target);
    return x;
}
//搜索不完全有序的区间
int searchNo(int* nums, int left, int right, int target){
    int mid = (left + right) / 2;
    int x1 = -1, x2 = -1;
    if(left > right)
    {
        return -1;
    }
    if(nums[mid] == target)
    {
        return mid;
    }
    if(nums[mid] > nums[0])//说明左区间有序，否则右区间有序
    {
        //将target与区间两个端点，而不仅仅是mid进行比较，这有利于判断是否放弃一个区间
        if(nums[0] <= target && target <= nums[mid]) //nums[mid-1]是否可能非法内存访问？
        {
            x1 = searchSorted(nums, 0, mid-1, target);
        }
        else
        {
            x2 = searchNo(nums, mid+1, right, target);
        }
    }
    else//右区间有序
    {
        if(nums[mid] <= target && target <= nums[right])
        {
            x2 = searchSorted(nums, mid+1, right, target);
        }
        else
        {
            x1 = searchNo(nums, 0, mid-1, target);
        }
    }
    if(x1 != -1)
    {
        return x1;
    }
    return x2;
}
//搜索有序区间
int searchSorted(int *nums, int left, int right, int target){
    int mid = (left + right) / 2;
    int x = -1;
    if(left > right)
    {
        return -1;
    }
    if(nums[mid] == target)
    {
        return mid;
    }
    if(target < nums[mid])
    {
        x = searchSorted(nums, left, mid-1, target);
    }
    else if(nums[mid] < target)
    {
        x = searchSorted(nums, mid+1, right, target);
    }
    return x;//x是不是-1都可以return
}

4.运行结果

成功通过！

5.小结

感觉在编码之前，仅仅规划大致的算法步骤还不够。也许我还需要一个中间的层次，像伪代码那样，即可以仔细考虑算法过程中的细节，又不必理会太多具体有关编程语言的细节。