数组有序时常用二分法来查找，时间复杂度降到O(logn)。旋转的有序数组也可以使用二分法，通过讨论mid所指元素在数组中的位置来重新确定搜索范围。
153，寻找旋转排序数组中的最小值，medium
假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。
请找出其中最小的元素。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
|
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
|
示例 3：
提示：
1 <= nums.length <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数都是 唯一 的
nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转
|
题解
在找到 mid 时，要确定最小值在 mid 的左侧还是右侧。
代码
class Solution {
public int minArray(int[] numbers) {
int n = numbers.length;
if(n == 0) return 0;
int l = 0;
int r = n - 1;
while(l < r){
int mid = l + (r - l) / 2;
if(numbers[mid] < numbers[r]){
r = mid;
}
else if(numbers[mid] > numbers[r]){
l = mid + 1;
}
else r--;
}
return numbers[l];
}
}
|
33，搜索旋转排序数组，medium
整数数组 nums 按升序排列，数组中的值 互不相同 。
升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
|
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
|
示例 3：
输入：nums = [1], target = 0
输出：-1
|
题解
在二分查找过程中通过 mid 将数组分割为两部分，[l, mid] 和 [mid+1, r]，通过比较大小可确定哪部分是有序的。确定nums[mid]在左部分还是右部分，再确定target在mid的左边还是右边，从而调整left和right。
代码
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target) return mid;
if(nums[mid] >= nums[left]){
if(nums[mid] > target && target >= nums[left]) right = mid - 1;
else left = mid + 1;
}
else{
if(nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
}
|
面试题10.03
搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。 示例1:
输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）
示例2:
输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出：-1 （没有找到）
|
题解
注意此题与上面题的区别在于可以有重复元素。且已旋转多次。
代码
class Solution {
public int search(int[] arr, int target) {
int l = 0, r = arr.length - 1;
while(l <= r){
int mid = l + (r - l) / 2;
if(arr[l] == target)
return l;
else if(arr[l] == arr[mid])
l++;
else if(arr[mid] > arr[l]){
if(target > arr[l] && target <= arr[mid]) r = mid;
else l = mid + 1;
}
else{
if(target > arr[mid] && target < arr[l])
l = mid + 1;
else r = mid ;
}
}
return -1;
}
}
|
下面这道题很类似了，换汤不换药
81，搜索旋转排序数组Ⅱ，medium
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
示例 1： 输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
|
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
|
代码
class Solution {
public boolean search(int[] arr, int target) {
int l = 0, r = arr.length - 1;
while(l <= r){
int mid = l + (r - l) / 2;
if(arr[l] == target)
return true;
else if(arr[l] == arr[mid])
l++;
else if(arr[mid] > arr[l]){
if(target > arr[l] && target <= arr[mid]) r = mid;
else l = mid + 1;
}
else{
if(target > arr[mid] && target < arr[l])
l = mid + 1;
else r = mid ;
}
}
return false;
}
}
|