首页 > 代码库 > Search in Rotated Sorted Array I

Search in Rotated Sorted Array I

2024-07-15 10:51:06   221人阅读

要搜索的对象是一个rotated sorted array，所以从直觉上时间复杂度应该不会超过O(logn)。起初我想尝试修改binary search来解决这个问题，但仔细思考后发现在不断search的过程中，search的boundary是比较难确定的。解决这个题目的另一个思路就是先把pivot找出来，在这里我把pivot定义为数组中最小的那个数。所以下面要解决的便是能不能在O(logn)的时间找到pivot。沿着这个思路，然后综合rotated sorted array的特征，可以用类似binary serach的方法找到pivot。pivot具有如下特征：pivot左侧和右侧的数均大于pivot本身。而搜索方向的确定可以根据比较当前搜索到的数与A[0]来判断，如果A[current] >= A[0]说明pivot在[current,n]的范围内，反之pivot在[0,current-1]范围内。不过要注意没有pivot的特殊情况，即array是sorted但没有被rotated。

在得到pivot后，我们便可以在pivot划分的两个区域内分别用binary search搜索target。时间复杂度为O(logn)。

 1 class Solution { 2 public: 3     int search(int A[], int n, int target) { 4         int pivot = search_pivot(A,0,n-1); 5         if(pivot == -1) return binary_search(A,0,n-1,target); 6         if(target > A[pivot-1] || target < A[pivot] || target < A[0] && target > A[n-1]) return -1; 7         if(target >= A[0]) return binary_search(A,0,pivot-1,target); 8         else return binary_search(A,pivot,n-1,target); 9     }10     int search_pivot(int A[], int left, int right){11         if(left >= right) return -1;12         int mid = (left + right)/2;13         if(A[mid] < A[0]){14             if(A[mid-1]>A[mid]) return mid;15             else  return search_pivot(A, left, mid-1);16         }else {17             if(A[mid+1]<A[mid]) return mid+1;18             else return search_pivot(A,mid + 1,right);19         }20     }21     int binary_search(int A[], int left, int right, int target){22         if(left > right) return -1;23         int mid = (left + right)/2;24         if(A[mid] == target) return mid;25         if(A[mid] > target) return binary_search(A,left,mid-1,target);26         if(A[mid] < target) return binary_search(A,mid+1, right,target);27     }28 };

 


联系
我们