leetcode第33题,题目比较简单,相当于就是在前后部分都是有序的序列中找target.马上就会想到二分查找,关键是先找到两个有序序列的分界点,同样分界点也是用二分查找找。容易忽略的点是可能整个序列没有rotate,就是一个上升序列。
class Solution {
public: int search(vector<int>& nums, int target) { int nLen=nums.size(); if(nLen==0) return -1; if(nLen==1) if(nums[0]==target) return 0; else return -1; int leftMin=nums[0]; int rightMax=nums[nLen-1]; int left=0; int pior; int result=-1; int right=nums.size()-1; if(leftMin>rightMax) { while(left<=right) { int mid=(left+right)/2; if(nums[mid]>=leftMin) { if(nums[mid+1]<nums[mid]) { pior=mid; break; } left=mid+1; } if(nums[mid]<=rightMax) { right=mid-1; } } }else pior=nLen-1; if(target>=leftMin)//在左边序列中找 { int left=0,right=pior; while(left<=right) { int mid=(left+right)/2; if(nums[mid]==target) { result=mid; break; } else if(nums[mid]>target) right=mid-1; else left=mid+1; } } else//在右边序列中找 { int left=pior+1,right=nLen-1; while(left<=right) { int mid=(left+right)/2; if(nums[mid]==target) { result=mid; break; } else if(nums[mid]>target) right=mid-1; else left=mid+1; } } return result; } };