leetcode33-- Search in Roted Sorted Array(被面过)

# 小郑之家~

### 题目

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).

Example 1:

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

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



### 解答


class Solution(object):

def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""

if len(nums) == 0:
return -1

start, end = 0, len(nums)-1
while start+1<end:
mid = start+(end-start)/2
if nums[mid]==target:
return mid
elif nums[mid] > nums[start]:
if target>=nums[start] and target<=nums[mid]:
end = mid
else:
start = mid
else:
if target>=nums[mid] and target<=nums[end]:
start = mid
else:
end = mid
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1



class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty()) return -1;

int start=0, end = nums.size()-1;

while(start+1<end){
int mid = start+(end-start)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]>nums[start]){
if(nums[start]<=target && target<=nums[mid]){
end = mid;
}else{
start = mid;
}
}else{
if(nums[mid]<=target && target<=nums[end]){
start = mid;
}else{
end = mid;
}
}
}

if(nums[start]==target) return start;
if(nums[end]==target) return end;
return -1;
}
};