解题思路
方法一、直接暴力搜索吧
方法二、若未旋转,则直接二分查找,若存在旋转,则找出分割点,在左右两个子数组分别进行二分查找。
代码
方法一、暴力搜索
class Solution {
public:bool search(int A[], int n, int target) {bool flag = false;for(int i = 0;i < n;i++){if(A[i] == target){flag = true;}}return flag;}
};
方法二、
class Solution {
public:bool search(int A[], int n, int target) {if(A[0] < A[n - 1])return binarySearch(A,0,n - 1,target);else{int i = 0;for(;i < n;i++){if(A[i] > A[i + 1])break;}return binarySearch(A,0,i,target) || binarySearch(A,i+1,n - 1,target);}}bool binarySearch(int A[],int low,int high,int target){bool flag = false;while(low <= high){int mid = (low + high) / 2;if(A[mid] == target){flag = true;break;}else if(A[mid] > target)high = mid - 1;elselow = mid + 1;}return flag;}