导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一
    2. 方法二

LeetCode-33.Search in Rotated Sorted 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.

翻译

假设一个有序数组,以一个未知的枢轴旋转了。(例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2)。
给出一个target值进行搜索。如果在数组中找到了则返回index,否则返回-1。
你可以认为数组中没有重复元素。

方法一

遍历……

1
2
3
4
5
6
7
8
public class Solution {
public int search(int[] nums, int target) {
for (int i = 0; i < nums.length; i++)
if (nums[i] == target)
return i;
return -1;
}
}

方法二

对于题中的旋转数组,一定是分成左右两部分,两部分分别递增,而左半部分所有元素都比右半部分所有元素大。
采取二分策略,中点一定落在左或右部分。对于有序的部分,可以轻易判断出是否在区间上,如果在,则留下有序部分;如果不在,则继续在另外的分成左右两部分的数组中查找:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public int search(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) return mid;
if (nums[low] <= nums[mid]) { // 等号很重要,因为low可能等于mid
if (nums[low] <= target && target < nums[mid]) high = mid - 1;
else low = mid + 1;
} else {
if (nums[mid] < target && target <= nums[high]) low = mid + 1;
else high = mid - 1;
}
}
return -1;
}
}

参考:
https://segmentfault.com/a/1190000003811864