首页 > 代码库 > Search in Rotated Sorted Array -- leetcode
Search in Rotated Sorted Array -- leetcode
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.
版本一,递归实现
在leetcode上,实际执行时间为7ms。
算法基本思路依据为,将区间折半后,必有一半是递增的(左端点的值小于右端点的值)。
看要找的值在此区间中没,若在,在此区间继续搜索。否则,进入另一半区间。
class Solution { public: int search(int A[], int n, int target) { if (!n) return -1; bool first = false; const int mid = (n-1) / 2; if (A[mid] == target) return mid; else if ((A[0] <= target && target < A[mid])) first = true; else if (A[mid] < target && target <= A[n-1]) first = false; else if (A[0] > A[mid]) first = true; if (first) return search(A, mid, target); else { const int result = search(A+mid+1, n-mid-1, target); return result != -1 ? result + mid+1 : -1; } } };
版本2:非递归实现
其思路与上同。 只是将上面的代码加入了while循环。
执行时间也是7ms。
class Solution { public: int search(int A[], int n, int target) { int low = 0; int high = n - 1; while (low <= high) { bool first = false; const int mid = low + (high - low) / 2; if (A[mid] == target) return mid; else if ((A[0] <= target && target < A[mid])) first = true; else if (A[mid] < target && target <= A[n-1]) first = false; else if (A[0] > A[mid]) first = true; if (first) high = mid - 1; else low = mid + 1; } return -1; } };
Search in Rotated Sorted Array -- leetcode
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。