• 模板
• 例题
  • 33.搜索旋转排序数组
    • 描述
    • 示例1
    • 示例2
    • 示例3
    • 提示
    • 思路
    • 代码
  • 153.寻找旋转排序数组中的最小值
    • 描述
    • 示例1
    • 示例2
    • 示例3
    • 提示
    • 代码

模板

left,right=1,n
while left<=right:
    mid=left+(right-left)//2
    if 条件:
        right=mid+1
    else:
        left=mid-1

1. 定义左右边界
2. 左边界小于右边届时进入循环体
3. 取中间数，使用left+(right-left)//2是防止越界的问题
4. 根据业务条件不断的向中间移动left和right

例题

33.搜索旋转排序数组

描述

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 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

提示

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4

思路

直接先套用模板

n=len(nums)
left,right=0,n-1
while left<=right:
    mid=left+(right-left)//2
    if 条件:
        right=mid-1
    else:
        left=mid+1

然后补充条件

首先 如果 nums[mid]=target 那么就可以直接返回

if nums[mid]==target: return mid

再次nums[mid]肯定落在nums数组的前半段或后半段，有题目可知，nums是有两个升序的序列组成，如果nums[left]<=nums[mid]那nums[mid]落在前半段的升序列里，否则就落在了后半段的升序列里。
如果落在了前段的升序里，则用nums[l]、nums[mid]与target进行比较

if nums[l]<=target<nums[mid]:
    r=mid-1
else:
    l=mid+1

否则

if nums[mid]<target<=nums[r]:
    r=mid-1
else:
    l=mid+1

代码

class Solution(object):
    def search(self, nums, target):
        #在取中间数的时候，分3种情况
        # 1 nums[mid]==target 就直接返回mid，找到结果了
        # 2 nums[mid]>=nums[l] 既落在左边的序列里
        # 3 否则 就落在右边的序列里
        n=len(nums)
        l,r=0,n-1
        while l<=r:
            mid=l+(r-l)//2
            if nums[mid]==target:
                return mid
            if nums[l]<=nums[mid]:#说明左边是有序的
                if nums[l]<=target<nums[mid]:
                    r=mid-1
                else:
                    l=mid+1
            else:#否则右边有序
                if nums[mid]<target<=nums[r]:
                    r=mid-1
                else:
                    l=mid+1
        return -1

153.寻找旋转排序数组中的最小值

描述

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例1

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例2

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例3

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

代码

class Solution(object):
    def findMin(self, nums):
        # return sorted(nums)[0]
        # return min(nums)
        n=len(nums)
        left,right=0,n-1
        while left<=right:
            mid=(left+right)//2
            print(left,mid,right)
            if nums[mid]<nums[right]:
                right=mid
            else:
                left=mid+1
        return nums[mid]