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. Subscribe to see which companies asked this question.
题目来自此处
一开始以为题意是找旋转的那个标志位（误） 既然是寻找，那么最小的时间复杂度是 O(logn) 。用了 O(n) 的算法即相当于直接查找…… 那么只能用二分查找才能保证最快的查找速度，但是二分查找是建立在有序表的基础上的，怎么操作呢？ 先“二分查找”出数组进行旋转的标志位，标志位两边分别是数组的最大、最小值，根据这个再对数组进行分别“二分查找”处理就好了~
class Solution { public: int search(vector<int>& nums, int target) { int size = nums.size(); if (size==0) return -1; int low = 0, high = size - 1; while (low < high){ int mid = (low + high) / 2; if (nums[mid] > nums[high]) //表明当前mid到high之间不按升序排列 low = mid + 1; else high = mid; }//找出标志位（最小值） int flag = low; if (target >= nums[flag] && target <= nums[size - 1]) return bin_method(nums, flag, size - 1,target); else if (target >= nums[0] && target <= nums[flag-1]) return bin_method(nums, 0, flag-1,target); else return -1; } int bin_method(vector<int> num, int low, int high,int target){ if (num[low] == target) return low; else if (num[high] == target) return high; else{ while (low < high){ int mid = (low + high) / 2; if (num[mid] == target) return mid; else if (num[mid] > target) high = mid; else low = mid+1; } return -1; } } };当然可把数组的旋转部分当做原数组的扩展进行处理，就不用分步讨论，代码可以大大缩短~ 最后吐槽下md写公式的预览效果跟发表博客之后的效果大相径庭。。
