leetcode33 Search in Rotated Sorted Array

Suppose a sorted array 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.

 1 class Solution {
 2 public:
 3     int search(vector<int>& nums, int target) {
 4         int a=0,b=nums.size()-1;
 5         while(a<=b)
 6         {
 7             int m=a+(b-a)/2;
 8             if(nums[m]==target)
 9                 return m;
10             if(nums[m]<nums[a])
11             {
12                 if(nums[a]<=target)
13                     b=m-1;
14                 else
15                     a++;
16             }
17             else
18             {
19                 if(nums[a]>target)
20                     a=m+1;
21                 else if(nums[a]==target)
22                     return a;
23                 else
24                     a++;
25             }
26             
27         }
28         return -1;
29     }
30 };

View Code