说明
由于题目相对简单，所以代码直接在课程视频中。以后一定注意，保留源码。
题目
已知整数数组nums，先按升序排序后，再旋转。旋转k位后，元素分别为nums[k],nums[k+1]...nums[0]...nums[k-1]。请查找target 是否存在，如果存在返回所在索引；否则返回-1。假定nums没有重复的元素。
假定排序后的数组为{1,2,3,4,5}。
旋转0位：不变。
旋转1位：{2,3,4,5,1}
旋转2位：{3,4,5,1,2}
旋转3位：{4,5,1,2,3}
旋转4位：{5,1,2,3,4}
解题思路
观察后，可以得到如下结论：
旋转数组，可以拆分成左右两个升序数组，且左数组的任意元素都大于右数组的任意元素。
分两步：
- 找到数组的分界线RBegin，[0,RBegin)是左数组，[RBegin,n)是右数组。特殊情况：只有一个升序数组，则RBegin为0，左数组为空。
- 如果是小于等于nums.back()，在右边找；否则在左边找。升序寻找元素之前已经讲过了，就不累赘了。
- 寻找RBegin
nums[mid] < nums.back() |
扔掉右边，不扔mid |
nums[mid] == nums.back() |
扔掉右边，不扔mid |
nums[mid] > nums.back() |
扔掉左边,扔掉mid |
故用左开右闭空间。
代码
class Solution { public: int search(vector<int>& nums, int target) { int rBegin = FindRBegin(nums); if (target <= nums.back()) { return Find(nums, rBegin, nums.size(), target); } return Find(nums, 0, rBegin, target); } int FindRBegin(const vector<int>& nums) { int left = -1, r = nums.size()-1;//左开右闭 while (r - left > 1) { const int mid = left + (r - left) / 2; if (nums[mid] <= nums.back()) { r = mid; } else { left = mid; } } return r; } int Find(const vector<int>& nums, int left, int r, int target) { while (r - left > 1) { const auto mid = left + (r - left) / 2; if (nums[mid] <= target) { left = mid; } else { r = mid; } } return (target == nums[left]) ? left : -1; } }; int main() { vector<int> vNums = {1,2,3,4,6}; auto res = Solution().search(vNums, 4); std::cout << "index:" << res; if (-1 != res) { std::cout << " value:" << vNums[res]; } }
注意
开发及测试操作系统：Windows10（安装的时候没注意，安装成了英文版）
开发及测试环境：Microsoft Visual Studio 2022
如果还不明白，请看我的视频；如果看完视频，还是不明白，请下载源码后，直接修改。
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17 或Win10 VS2022 Ck++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版
