Worst case is O(n). Average is O(log n).

To understand low++ and high--, consider below 2 cases-

- low++ => [3,1,2,2,2],search value=1,rotation shift is 1
- high-- => [4,4,10,2],search value=10,rotation shift is 3

```
public class Solution {
public boolean search(int[] nums, int target) {
int low = 0,
high = nums.length-1,
mid = 0;
while(low <= high){
mid = low + (high-low)/2;
if(nums[mid] == target) return true;
if(nums[mid] > target){
if(nums[low] > target) low++;
else high = mid-1;
}
else if(nums[mid] < target){
if(nums[high] < target) high--;
else low = mid+1;
}
}
return false;
}
}
```