(i.e.,0 1 2 4 5 6 7might become4 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.
-1
class Solution {
public:
bool search(int A[], int n, int target) {
for(int i = 0;i<n;i++)
{
if(A[i]==target)
return true;
}
return false;
}
};
class Solution {
public:
bool search(int A[], int n, int target) {
int low = 0, high = n - 1;
while(low <= high){
int mid = (low + high) / 2;
if(A[mid] == target)
return true;
if(A[low] == A[mid] && A[mid] == A[high]){
low++;
high--;
}else if(A[low] <= A[mid]){ //left sorted
if(A[low] <= target && A[mid] > target){
high = mid - 1;
}
else
low = mid + 1;
}else if(A[mid] <= A[high]){
if(A[mid] < target && A[high] >= target){
low = mid + 1;
}
else
high = mid - 1;
}
}
return false;
}
};
#
#
# @param A int整型一维数组
# @param target int整型
# @return bool布尔型
#
class Solution:
def search(self , A , target ):
# write code here
return target in A
leetcode117search-in-rotated-sorted-array
原文：https://www.cnblogs.com/hrnn/p/13413399.html