33. Search in Rotated Sorted Array

Description：
Suppose an array sorted in ascending order 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.
Your algorithm’s runtime complexity must be in the order of O(log n).
Difficulty：Medium
Example:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

方法1：二分查找

• Time complexity : $O\left ( logn \right )$O(logn)
• Space complexity : $O\left ( 1 \right )$O(1)
  思路：
  因为数组被旋转了，分成两个部分，左边部分和右边部分，分开来看都是递增的，但是要看清楚边界关系，如下图
  
  这里面要注意的两种情况：
  mid在左侧，但是target在右侧，l = mid + 1；
  mid在右侧，但是target在左侧，r = mid - 1

class Solution {
public:
	vector<int> searchRange(vector<int>& nums, int target) {
		int start, end;
		int l = 0, r = nums.size() - 1, mid;
		while (l <= r) {
			mid = (l + r) / 2 ;
			if (nums[mid] < target) 
				l = mid + 1;
			else if (nums[mid] > target)
				r = mid - 1;
			else {
				for (start = mid; start >= 0; start--) {
					if (nums[start] != target) {
						break;
					}
				}
				for (end = mid; end < nums.size(); end++) {
					if (nums[end] != target) {
						break;
					}
				}
				return vector<int>({ start+1, end-1 });
			}
		}
		return 	vector<int>({ -1, -1 });
	}
};