153. 寻找旋转排序数组中的最小值
二分查找过程中，比较mid与right（而非left）的原因：
以 [1,2,3,4,5,6,7] 为例，分以下情况- 若[1,2,3,4,5,6,7] 左<中，中<右。最小值在最左边， 所以更新 右指针
- 若[6,7,1,2,3,4,5] 左>中，中<右。最小值在mid左边，所以更新 右指针
- 若[4,5,6,7,1,2,3] 左<中，中>右。最小值在mid右边，所以更新 左指针
可见，当中<右时（情况1,2），都是更新右指针，中>右时 （情况3），都是更新左指针（因为是找最小值，最小值偏左，所以mid和右指针进行比较，更有区分度）。 但是左<中时 （情况1,3）,指针更新不统一，讨论起来较麻烦。
循环条件l<r:
- 若
nums[mid]>nums[r],说明mid在第一个递增序列，最小值在mid右边，所以l=mid+1 （情况3）- 若
nums[mid]<=nums[r],说明mid在第二个递增序列，最小值在mid处或mid左边，所以r=mid （情况2, 或者如[3,4,0,1,2]）
class Solution(object):
def findMin(self, nums):
left=0
right=len(nums)-1
while left<right:
mid=left+(right-left)//2
if nums[mid]>nums[right]:
left=mid+1
else:
right=mid
return nums[left]154. 寻找旋转排序数组中的最小值 II
此题与上一题的区别是，增加了重复元素,所以循环条件略有区别，增加了nums[mid]==nums[r]等于时的特判，用right-=1跳过重复元素，使得right慢慢向左跳
循环条件l<r:
- 若
nums[mid]>nums[r],说明mid在第一个递增序列，最小值在mid右边，所以l=mid+1 （情况3）- 若
nums[mid]<nums[r],说明mid在第二个递增序列，最小值在mid处或mid左边，所以r=mid （情况2, 或者如[3,4,0,1,2]）- 若
nums[mid]=nums[r],r 向左慢慢跳，所以r-=1 （如[1,0,1,1,1]）
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left=0
right=len(nums)-1
while left<right:
mid=left+(right-left)//2
if nums[mid]>nums[right]:
left=mid+1
elif nums[mid]<nums[right]:
right=mid
else:
right-=1
return nums[left]
33. 搜索旋转排序数组
方法1：找到数组中的最小值后，在第一或第二递增区域内找目标值
根据上题”153. 寻找旋转排序数组中的最小值” 可以得到最小值，若将最小值minIdx作为旋转点，则有
- 若最小值下标为0，说明序列是单调递增的，所以在
0 - n-1范围内进行二分查找- 若
target>=nums[0],说明target在第一段递增序列内，所以在nums[0:minIdx]范围内进行二分查找- 若
target<nums[0],说明target需要在第二段递增序列内找，所以在nums[minIdx:]范围内进行二分查找
- 如果目标值不在第二递增序列中，则返回-1（如
[4,5,6,7,0,1,2]中找target 3），否则返回minIdx+binarySearch(nums[minIdx:],target)的结果
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
# 找到最小值的下标
def findMin(nums):
l=0
r=len(nums)-1
while l<r:
mid=l+(r-l)//2
if nums[mid]>nums[r]:
l=mid+1
else:
r=mid
return l
# 普通的二分查找，用于确定目标值下标
def binarySearch(nums,target):
l=0
r=len(nums)-1
while l<=r:
mid=l+(r-l)//2
if nums[mid]==target:
return mid
elif nums[mid]>target:
r=mid-1
else:
l=mid+1
return -1
minIdx=findMin(nums)
if minIdx==0: #单调递增，在整个范围内寻找
return binarySearch(nums,target)
elif target>=nums[0]: # 在第一个递增序列内找
return binarySearch(nums[0:minIdx],target)
else: # target<nums[0]: # 在第二个递增序列内找
# 如果目标值不在第二递增序列中，则返回-1，否则返回 minIdx+tmp
tmp=binarySearch(nums[minIdx:],target)
return -1 if tmp==-1 else minIdx+tmp
方法2：直接二分查找,在严格的递增序列内找target，其余情况取反
- 设置左右指针
nums[mid]==target时，说明已找到目标值，返回 mid （也是while的结束条件）当nums[mid]>=nums[l]时（注意这里要取等号，使得满足递增序列只有一个元素的情况也符合(如[3,1])），说明左边是递增序列，- 若target在递增序列内，则更新右指针
- 其他情况更新左指针 （target 在mid的右边，所以更新左指针）
- 否则当
nums[mid]<nums[l]时，说明右边是递增序列- 若target在递增序列内，则更新左指针
- 其他情况更新右指针 （target 在mid的左边，所以更新右指针）
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
n=len(nums)
l=0
r=n-1
while l<=r:
mid=l+(r-l)//2
# 找到后，结束循环，跳出
if nums[mid]==target:
return mid
# 左边是递增序列
if nums[mid]>=nums[l]:
# target 若在递增序列内，则更新右指针
if nums[l]<=target<nums[mid]:
r=mid-1
else: # 剩余情况更新左指针
l=mid+1
# 右边是递增序列
elif nums[mid]<nums[l]:
# target 若在递增序列内，则更新左指针
if nums[mid]<target<=nums[r]:
l=mid+1
else: # 剩余情况更新右指针
r=mid-1
return -1 # 不满足条件时，返回-1
81. 搜索旋转排序数组 II
与上题相比，本题增加了重复元素。因此，若检测到重复元素，则左（右）指针要跳，直到不重复：
如[1,1,1,1,2,1], 可保证跳过相邻的相同元素
与上题相比，增加如下判断：if nums[mid]==nums[l]==nums[r]: l+=1 r-=1
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
n=len(nums)
l=0
r=n-1
while l<=r:
mid=l+(r-l)//2
# 找到后，结束循环，跳出
if nums[mid]==target:
return True
# ******与上题相比，增加的部分****** #
"""
如[1,1,1,1,2,1], 可保证跳过相邻的相同元素
"""
if nums[mid]==nums[l]==nums[r]:
l+=1
r-=1
# ******与上题相比，增加的部分****** #
# 左边是递增序列
elif nums[mid]>=nums[l]:
# target 若在递增序列内，则更新右指针
if nums[l]<=target<nums[mid]:
r=mid-1
else: # 剩余情况更新左指针
l=mid+1
# 右边是递增序列
elif nums[mid]<nums[l]:
# target 若在递增序列内，则更新左指针
if nums[mid]<target<=nums[r]:
l=mid+1
else: # 剩余情况更新右指针
r=mid-1
return False # 不满足条件时，返回-1
