首页 > 代码库 > leetcode 题解：Search in Rotated Sorted Array II （旋转已排序数组查找2）

leetcode 题解：Search in Rotated Sorted Array II （旋转已排序数组查找2）

2024-07-10 17:48:45   212人阅读

题目：

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

说明：

     1）和1比只是有重复的数字，整体仍采用二分查找

     2）方法二 ：

 

 

 

 

 

实现：

   一、我的实现：

 1 class Solution { 2 public: 3     bool search(int A[], int n, int target) { 4         if(n==0||n==1&&A[0]!=target) return false; 5         if(A[0]==target) return true; 6         int i=1; 7         while(A[i-1]<=A[i])  i++; 8          9         bool pre=binary_search(A,0,i,target);10         bool pos=binary_search(A,i,n-i,target);11         return pre==false?pos:pre;12     }13 private:14     bool binary_search(int *B,int lo,int len,int goal)15     {16         int low=lo;17         int high=lo+len-1;18         while(low<=high)19         {20             int middle=(low+high)/2;21             if(goal==B[middle])//找到，返回index22                return true;23             else if(B[middle]<goal)//在右边24                low=middle+1;25             else//在左边26                high=middle-1;27         }28         return false;//没有，返回-129     }30 };

二、网上开源实现：

 1 class Solution { 2 public: 3     bool search(int A[], int n, int target) { 4          int low=0; 5          int high=n-1; 6          while(low<=high) 7          { 8             const int middle=(low+high)/2; 9             if(A[middle]==target) return true;10             if(A[low]<A[middle])11             {12                if(A[low]<=target&&target<A[middle])13                   high=middle-1;14                else15                   low=middle+1;16             }17             else if(A[low]>A[middle])18             {19                if(A[middle]<target&&target<=A[high])20                   low=middle+1;21                else 22                   high=middle-1;23             }24             else25                 low++;26          }27          return false;28     }29 };

 


联系
我们