leetcode 33. Search in Rotated Sorted Array

xiaoxiao2021-02-28  31

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;                         } };
转载请注明原文地址: https://www.6miu.com/read-1450346.html

最新回复(0)