首页 > 代码库 > [Leetcode] Search In Rotated Sorted Array (C++)
[Leetcode] Search In Rotated Sorted Array (C++)
题目：
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.
Tag:
Array; Binary Search
体会：
这道题和Find the Minimum In Rotated Sorted Array肯定是有联系啦，毕竟给的都是Rotated Sorted Array这种结构。思路是：从middle处开始左右两部分，一部分是sorted的了，另一部分rotated或者sorted。我们要去分析sorted的那个部分。假设左边是sorted部分，如果A[left] <= target < A[mid]，那么target一定只可能出现在这个部分，otherwise，出现在另外一部分。如果右边是sorted，同理。
1 class Solution { 2 public: 3 int search (int A[], int n, int target) { 4 int low = 0; 5 int high = n - 1; 6 7 while (low <= high) { 8 int mid = low + (high - low) / 2; 9 10 if (A[mid] == target) {11 return mid;12 }13 14 if (A[mid] < A[high]) {15 // right part is sorted, left is rotated part 16 if (A[mid] < target && target <= A[high]) {17 // target must be in right part18 low = mid + 1;19 } else {20 // target must be left part21 high = mid - 1;22 }23 } else {24 // left part is sorted25 if (A[low] <= target && target < A[mid]) {26 high = mid - 1;27 } else {28 low = mid + 1;29 }30 }31 }32 return -1;33 }34 };
[Leetcode] Search In Rotated Sorted Array (C++)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。