假设一个按升序排序的数组在某个未知的枢轴处旋转。 (即,[1, 4, 6, 8, 11, 13, 15]
可能变为 [8, 11, 13, 15, 1, 4, 6]
)。
您将获得要搜索的目标值。 如果在数组中找到返回它的索引,否则返回-1。
您可以假设数组中不存在重复项。 你的算法的运行时复杂度必须在 O(log n) 的数量级。
示例 1:
Input: nums = [8, 11, 13, 15, 1, 4, 6], target = 1
Output: 4
示例 2:
Input: nums = [1, 4, 6, 8, 11, 13, 15], target = 3
Output: -1
虽然整个数组不是从左到右排序的,但是枢轴左侧和枢轴右侧的子数组仍然会被排序。 我们可以利用这一事实并应用二分查找以 O(log(n))
时间复杂度在数组中查找元素。 为了清楚起见,以下是带有注释的问题的解决方案:
import java.util.Scanner;
class RotatedSortedArraySearch {
private static int search(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while(start <= end) {
int mid = (start + end)/2;
if(target == nums[mid]) {
return mid;
}
if(nums[start] <= nums[mid]) { // left array is sorted
if(target >= nums[start] && target < nums[mid]) { // target lies between start and mid index
end = mid-1;
} else {
start = mid+1;
}
} else { // right array is sorted
if(target > nums[mid] && target <= nums[end]) { // target lies between mid and end index
start = mid+1;
} else {
end = mid-1;
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; i++) {
nums[i] = keyboard.nextInt();
}
int target = keyboard.nextInt();
keyboard.close();
System.out.printf("Search(%d) = %d%n", target, search(nums, target));
}
}
# Output
$ javac RotatedSortedArraySearch.java
$ java RotatedSortedArraySearch
7
8 11 13 15 1 4 6
1
Search(1) = 4
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://www.callicoder.com/rotated-sorted-array-search/
内容来源于网络,如有侵权,请联系作者删除!