二分查找
寻找旋转排序数组中的最小值
假设一个按照升序排列的有序数组从某未知的位置旋转。
（比如
0 1 2 4 5 6 7可能变成4 5 6 7 0 1 2）。找到其中最小的元素。
你可以假设数组中不存在重复的元素。
首先判断\(m\) 在左侧蓝色区域，还是右侧橙色区域，在蓝色区域说明最小值在右侧，令\(l=m+1\)，在橙色区域说明最小值在左侧，令\(h=m\)。这里没有考虑重复值得情况，如果有重复值，
不满足第一个条件: \(nums[m] \le nums[h]\)
不满足第二个条件：\(nums[m] \ge nums[h]\)
也就是说：\(nums[m]==nums[h]\)
此时只需简单的令\(h=h-1\)即可，继续查找剩下的部分。
当然，如果数组没有旋转会怎样，直接返回\(nums[l]\)就行，上述的算法可以进行优化，
\(return \; nums[l] \; if\; nums[l] \le nums[h]\)
Python:
1
2
3
4
5
6
7
8
9
10
11
12class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l, h = 0, len(nums) -1
while l < h:
m = (l + h) >> 1
if nums[m] > nums[h]: l = m + 1
elif nums[m] < nums[h]: h = m
return nums[l]
寻找旋转排序数组中的最小值 II
这是问题 “在旋转排序阵列中查找最小值” 的进阶版：
如果允许重复，该怎么办？
这会影响时间复杂度吗？会如何影响和为什么？
假设一个按照升序排列的有序数组从某未知的位置旋转。
（比如
0 1 2 4 5 6 7可能变成是4 5 6 7 0 1 2）。找到其中最小的元素。
数组中可能存在重复的元素。
Python:
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l, h = 0, len(nums) -1
while l < h:
m = (l + h) >> 1
if nums[m] > nums[h]: l = m + 1
elif nums[m] < nums[h]: h = m
else: h -= 1
return nums[l]
搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回
-1。你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
1
2输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4示例 2:
1
2输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1查找某个元素和上述的找最小值框架一样，不同的是还要进行二次判断确认target的区间。
Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums: return -1
l, h = 0, len(nums) - 1
while l < h:
m = (l + h) // 2
if nums[m] > nums[h]:
if target > nums[m] or target <= nums[h]:
l = m + 1
else:
h = m
elif nums[m] < nums[h]:
if target > nums[m] and target <= nums[h]:
l = m + 1
else:
h = m
return l if nums[l] == target else -1
搜索旋转排序数组 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,0,1,2,2,5,6]可能变为[2,5,6,0,0,1,2])。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回
true，否则返回false。示例 1:
1
2输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true示例 2:
1
2输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false进阶:
- 这是 搜索旋转排序数组 的延伸题目，本题中的
nums可能包含重复元素。 - 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
if not nums: return False
l, h = 0, len(nums) - 1
while l < h:
m = (l + h) // 2
if nums[m] > nums[h]:
if nums[m] < target or target <= nums[h]:
l = m + 1
else:
h = m
elif nums[m] < nums[h]:
if nums[m] < target and target <= nums[h]:
l = m + 1
else:
h = m
else:
h -= 1
return nums[l] == target
- 这是 搜索旋转排序数组 的延伸题目，本题中的
