【每日算法Day 39】二分查找2
在学习了二分查找的基本思路与“搜索区间”相关的细节之后，来看一些二分查找的变种：旋转排序数组搜索特定值、搜索最小值、包含重复元素的问题。
# LeetCode 33. 搜索旋转排序数组 (opens new window)
# 题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
# 示例
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
2
# 解题思路
我们在本题中使用二分法后，要确定舍弃哪一半部分，而对于旋转排序数组，至少有一半部分是有序的（画图就知道了），我们找到有序的一半后就能确定target是否在这一半。然后收缩对应的边界即可。
public int search(int[] nums, int target) {
int left=0,right=nums.length-1;
while (left <= right) {
int mid=left+((right-left)>>1);
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) {//如果左边有序，注意=的特例
if (nums[left] <= target && nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
} else {//如果右边有序
if (nums[right] >= target && nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# LeetCode 81. 搜索旋转排序数组 II (opens new window)
# 题目描述
在上一题的基础上，不保证数组中没有重复元素，那么该如何解决？这对程序的时间复杂度有影响吗？
# 示例
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
2
# 解题思路
不保证数组中没有重复元素，就不能通过比较nums[left] <= nums[mid]来确认一半是否有序（例如[1,3,1,1,1]，3），那么对于nums[left]=nums[right]且不等于target的情况，就向内收缩left++,right--，不过这样做在最差情况下会将复杂度提升至O(N)。
public boolean search(int[] nums, int target) {
int left=0,right=nums.length-1;
while(left < right && nums[left] == nums[right]){
if(nums[left]==target) return true;
left++;
right--;
}
while (left <= right) {
int mid=left+((right-left)>>1);
if (nums[mid] == target) {
return true;
}
if (nums[left] <= nums[mid]) {//如果左边有序，注意=的特例
if (nums[left] <= target && nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
} else {//如果右边有序
if (nums[right] >= target && nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
}
return false;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# LeetCode 153. 寻找旋转排序数组中的最小值 (opens new window)
# 题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。
你可以假设数组中不存在重复元素。
# 示例
输入: [3,4,5,1,2]
输出: 1
2
# 解题思路
这一题也是剑指Offer面试题11，这一题如果数组中可以存在重复元素则也可以压缩两端或者直接遍历，采用压缩的方式就要注意一开始left可能是最小元素，需要在最后比较一下。此外，在先得知了最小值及其下标的情况下，结合nums[left]、nums[right]来做第一题可以直接判断target的搜索区间了。
public int findMin2(int[] nums) {
int left=0,right=nums.length-1;
while (left <= right) {
//实际上最终left==right时就返回了，不会跳出循环
if (nums[left]<=nums[right])
return nums[left];
int mid=left+((right-left)>>1);
if (nums[mid] >= nums[left]) {//如果左侧有序（单调增），则最小值一定在右侧
left=mid+1;
} else if (nums[mid] < nums[left]) {//左侧不是单调增，最小值在左侧（不排除mid）
right=mid;
}
}
return -1;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15