33. Search in Rotated Sorted Array
Description
描述：https://leetcode.com/problems/search-in-rotated-sorted-array/description/ 题意：在旋转有序数组中，查找指定的数，时间复杂度要求O(log n)。
Solution: (Java)
class Solution {
public int search(int[] nums
, int target
) {
int left
= 0, right
= nums
.length
-1;
int mid
;
while (left
<= right
) {
mid
= (left
+right
) / 2;
if (nums
[mid
] == target
)
return mid
;
if (nums
[mid
] < nums
[right
]) {
if (nums
[mid
] < target
&& target
<= nums
[right
])
left
= mid
+ 1;
else
right
= mid
- 1;
} else {
if (nums
[left
] <= target
&& target
< nums
[mid
])
right
= mid
- 1;
else
left
= mid
+ 1;
}
}
return -1;
}
}
思路
本题的思路是二分查找，但需要做一些变化，注意的点：
旋转有序数组有一个特性，就是总有左半边或者右半边是有序的，利用这一点，来确定二分查找时该缩小到左半边还是右半边；关键是确定左半边有序还是右半边有序：中间（mid）的数小于最右边（right）的数时，则右半边有序，否则左半边有序（与 left 比较也可以，注意要 mid 大于等于 left ）；确定哪边有序之后，再确定是否在有序的半边继续搜索或者换另一边。
