leetcode33 Search in Rotated Sorted Array
思路：
有意思的一道题。是一般的二分查找的一种变体，需要在二分过程中对各种情况进行分类讨论。
实现：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 class Solution 5 { 6 public: 7 int search(vector<int>& nums, int target) 8 { 9 int n = nums.size(); 10 int l = 0, r = n - 1, ans = -1; 11 while (l <= r) 12 { 13 int m = l + r >> 1; 14 if (nums[l] > nums[m]) 15 { 16 if (target == nums[m]) { ans = m; break; } 17 else if (target > nums[m]) 18 { 19 if (target > nums[r]) r = m - 1; 20 else l = m + 1; 21 } 22 else r = m - 1; 23 } 24 else 25 { 26 if (target == nums[m]) { ans = m; break; } 27 else if (target > nums[m]) l = m + 1; 28 else 29 { 30 if (target >= nums[l]) r = m - 1; 31 else l = m + 1; 32 } 33 } 34 } 35 return ans; 36 } 37 }; 38 39 int main() 40 { 41 int a[] = {4, 5, 6, 7, 0, 1, 2}; 42 int n = sizeof(a) / sizeof(int); 43 int target = 5; 44 vector<int> v(a, a + n); 45 cout << Solution().search(v, target) << endl; 46 return 0; 47 }