*Binary Search:*

```
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
if (n == 0) return -1;
int left = 0;
int right = n-1;
int mid = 0;
while (left <= right)
{
mid = left + (right-left) / 2;
if (target == nums[mid])
return mid;
//every time we check whether the left part(array[left] ... array[mid]) is in ascending order or the right part(array[mid] ... array[right]) is in ascending order
if (nums[left] <= nums[mid])
{
//if the left part is in ascending order, the next searthing depends on whether the target is in the left part
//if the target is in the range of left part(of course it may not exist in left part),it must not exist in the right part then we eliminate the right part,otherwise eliminate the left part
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
else
{
//likewise the right part is in ascending order,we can eliminate another part just check if the target is in range of right part
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}
};
```