本文主要是介绍Leetcode C++ 33. Search in Rotated Sorted Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Leetcode 33. Search in Rotated Sorted Array
原文：
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
解题思路：二分查找，但是需要判断边界值。假设nums的第一位是l，最后一位是r - 1，中位数m = (l + r) / 2。则有两种情况：第一种，前一半是正常的升序排列，后一半是还是旋转了的排序（nums[m] >= nums[l），在这种情况下判断目标t在哪一部分。第二种，后一半是正常的升序排列，前一半是还是旋转了的排序（nums[m] < nums[l），在这种情况下判断目标t在哪一部分。然后二分查找t的位置。
class Solution {
public:int search(vector<int>& nums, int target) {int l = 0;int t =target;int r = nums.size();while(l != r){//取中值int m = (l + r) / 2;if(nums[m] == t)return m;//第一种情况 前一半升序 后一半还是循环排序if(nums[m] >= nums[l]){//t在前半部分if(t >= nums[l] && t < nums[m])r = m;else//t在后半部分l = m + 1;}else{//第二种情况 前一半还是循环排序 后一半是升序//t在后半部分if(t > nums[m] && t <= nums[r - 1])l = m + 1;else//t在前半部分r = m;}}return -1;}
};
这篇关于Leetcode C++ 33. Search in Rotated Sorted Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
