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

news/2024/5/17 0:57:36/文章来源:https://blog.csdn.net/m0_63238256/article/details/127144245

文章目录

🚩 前言
1.题目描述
2.算法设计思路
3.算法实现
- bug记录
- 🧭 遇到问题（可跳过）
- 🌻 写在前面
- 我最初的通过代码（C语言）
4.运行结果
5.小结

🔥 该专栏作为算法题笔记，记录算法的思路、遇到的问题，以及能跑的代码，持续更新中！

推荐一款面试、刷题神器牛客网：👉开始刷题学习👈

🚩 前言

本文记录的是一个过程，若想快速获得解题思路，可直接从目录跳到这一部分：🌻 写在前面

1.题目描述

描述
有一个长度为 n 的按严格升序排列的整数数组 nums ，在实行 search 函数之前，在某个下标 k 上进行旋转，使数组变为
$[n u m s [k], n u m s [k + 1], ....., n u m s [n u m s . l e n g t h - 1], n u m s [0], n u m s [1], ......., n u m s [k - 1]]$
给定旋转后的数组 nums 和一个整型 target ，请你查找 target 是否存在于 nums 数组中并返回其下标（从0开始计数），如果不存在请返回-1。

数据范围： $\le n \le 10000,0 \le target \le 100000$
要求：空间复杂度 $O (1)$ ，时间复杂度 $O (n)$
例子，数组 $[0, 2, 4, 6, 8, 10]$ 在下标3处旋转之后变为 $[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 herefor(int i = 0; i < numsLen; i++){if(nums[i] == target){return i;}}return -1;
}

后面仔细看了题目和别人的讨论才发现，有一个重要的条件是数组在旋转之前是严格升序的。所有题目的意思是，为了将时间复杂度从 $O (n)$ 减小为 $O (l o g (n))$ $O(log(n))\Omicron(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 hereint mid = numsLen / 2;int x = -1;//注意不是初始化为 0x = 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
}