FIrst while loop look for index `h`

such that `a[h] > a[h+1]`

. If there's no rotation, both `l`

and `h`

will be set to the last index `last`

. Then compare `target`

with the first element `a[0]`

to decide whether to look for target in `a[0]`

to `a[h]`

or in `a[h+1]`

to `a[last]`

.

```
class Solution {
public:
int search(vector<int>& a, int target) {
int last = a.size()-1, l = 0, h = last, k = 0;
while (l < h) {
k = (l+h+1) >> 1;
if (a[k] < a[l])
h = k-1;
else
l = k;
}
if (target >= a[0])
l = 0;
else {
l = h+1;
h = last;
}
while (l <= h) {
k = l+h >> 1;
if (target < a[k])
h = k-1;
else if (target > a[k])
l = k+1;
else
return k;
}
return -1;
}
};
```