Java教程

【每日算法】二分查找法II

本文主要是介绍【每日算法】二分查找法II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 模板
  • 例题
    • 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]
这篇关于【每日算法】二分查找法II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!