首页 > 其他分享 >【leetcode】81. 搜索旋转排序数组 II

【leetcode】81. 搜索旋转排序数组 II

时间:2022-08-29 14:57:39浏览次数:54  
标签:数组 nums II 搜索 有序 81 leetcode target

原题地址:https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/

用循环遍历数组肯定能轻松找到target

但要尽可能减少操作步骤,一般跟顺序有关的都是用二分,关键是这题如何二分搜索

在找到中间位置mid后,数组被分成两个部分,一个有序一个无序,只要判断哪边是有序数组,然后再判断target是否在有序数组中,即可知道接下来要搜索哪一边。

如何判断哪一边是有序数组?可以把nums[mid]和nums[l]做比较,if now < nums[l] 右边有序,反之 左边有序

但还是会出现一个问题。就是重复如果now == nums[l],该怎么办?此时就把l右移一位即可(+1)

'''
二分后一边有序一边无序,看target是否在有序的那一边的范围内
'''


class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            now = nums[mid]
            if now == target:
                return True
            if now < nums[l]: # 右边有序
                if now < target and target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
            elif now > nums[l]: # 左边有序
                if nums[l] <= target and target < now:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                l = l + 1
        return False

  

标签:数组,nums,II,搜索,有序,81,leetcode,target
From: https://www.cnblogs.com/gogslow/p/16635936.html

相关文章

  • [LeetCode] 1470. Shuffle the Array
    Giventhearray nums consistingof 2n elementsintheform [x1,x2,...,xn,y1,y2,...,yn].Returnthearrayintheform [x1,y1,x2,y2,...,xn,yn].Example1:......
  • leetcode 227. Basic Calculator II 基本计算器 II(中等)
    一、题目大意给你一个字符串表达式s,请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。你可以假设给定的表达式总是有效的。所有中间结果将在[-23......
  • leetcode458 可怜的小猪
    思路:数学。实现:classSolution{public:intpoorPigs(intbuckets,intminutesToDie,intminutesToTest){intbase=minutesToTest/minutesToDie+1......
  • leetcode440 字典序的第K小数字
    思路:字典树思想。实现:1classSolution{2public:3//前缀prefix下的节点数量4usingll=longlong;5llget_count(llprefix,lln){6......
  • LeetCode 21. 合并两个有序链表
    题目题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的......
  • leetcode-1
    importjava.util.HashMap;/***<p>给定一个整数数组<code>nums</code>&nbsp;和一个整数目标值<code>target</code>,请你在该数组中找出<strong>和为目标值</strong......
  • leetcode-1470. 重新排列数组
    1470.重新排列数组图床:blogimg/刷题记录/leetcode/1470/刷题代码汇总:https://www.cnblogs.com/geaming/p/16428234.html题目思路开辟新的空间,装入元素。解法class......
  • LeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate
    原题链接在这里:https://leetcode.com/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate/题目:Youaregiventwointegers, x and y,whichrepresen......
  • LeetCode — 最小路径和
    LeetCode—最小路径和问题陈述给定一个mxn网格用非负数填充,找到一条从左上角到右下角的路径,该路径最小化沿其路径的所有数字的总和。笔记:您只能在任何时间点向下或......
  • LeetCode 854. K-Similar Strings
    原题链接在这里:https://leetcode.com/problems/k-similar-strings/题目:Strings s1 and s2 are k-similar (forsomenon-negativeinteger k)ifwecanswapthe......