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

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

2024-07-10 17:57:08   222人阅读

题目：

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 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）已排序数组查找采用二分查找

     2）关键找到临界点

实现：

一、我的代码：

     

 1 class Solution { 2 public: 3     int search(int A[], int n, int target) { 4         if(n==0||n==1&&A[0]!=target) return -1; 5         if(A[0]==target) return 0; 6         int i=1; 7         while(A[i-1]<A[i])  i++; 8          9         int pre=binary_search(A,0,i,target);10         int pos=binary_search(A,i,n-i,target);11         return pre==-1?pos:pre;12     }13 private:14     int 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 middle;23             else if(B[middle]<goal)//在右边24                low=middle+1;25             else//在左边26                high=middle-1;27         }28         return -1;//没有，返回-129     }30 };

二、网上开源代码：

 

 1 class Solution { 2 public: 3     int search(int A[], int n, int target) { 4         int first = 0, last = n-1; 5         while (first <= last)  6         { 7             const int mid = (first + last) / 2; 8             if (A[mid] == target) 9                 return mid;10             if (A[first] <= A[mid]) 11             {12                 if (A[first] <= target && target < A[mid])13                    last = mid-1;14                 else15                    first = mid + 1;16             } 17             else 18             {19                 if (A[mid] < target && target <= A[last])20                     first = mid + 1;21                 else22                     last = mid-1;23             }24         }25         return -1;26     }27 };

 


联系
我们