首页 > 代码库 > [LeetCode] Search in Rotated Array
[LeetCode] Search in Rotated Array
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,3,3,4,5,6,7]分为了两个有序数组[4,5,6,7]和[0,1,2]。且前面的那个有序数组的值全部大于后面的有序数组。
计算左边和右指针的中值mid。如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。按照上述的思路，第一个指针总是指向前面齐增数组的元素，而第二个指针总是指向后面递增子数组的元素。
时间复杂度O(lgN),空间复杂度O(1)
注意：此方法的要求与二分查找一样需要，仅适合于线性表的顺序存储结构，不适合于链式存储结构。而且数组的值不允许重复
相关题目：剑指offer面试题8
1 class Solution { 2 public: 3 int search(int A[], int n, int target) { 4 int low = 0; 5 int high = n - 1; 6 while (low <= high) { 7 int mid = (low + high) / 2; 8 if (A[mid] == target) { 9 return mid;10 } else if (A[low] <= A[mid]) {11 if (A[low] <= target && target <= A[mid]) {12 high = mid - 1;13 } else {14 low = mid + 1;15 }16 } else {17 if (A[mid] <= target && target <= A[high]) {18 low = mid + 1;19 } else {20 high = mid - 1;21 }22 }23 }24 25 return -1;26 }27 };
[LeetCode] Search in Rotated Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。