问题描述:
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
原问题链接:https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
问题分析
这个问题在之前的一篇文章里有过讨论。对于循环位移之后的排序数组来说,它相当于形成了两段递增的数组。我们还是可以用二分查找的方法去查找元素的。只是查找的过程稍微有点不一样。我们每次去中间值mid的时候,它可能落在前面的一个递增段上,也可能落在后面的一个递增段上。如果落在前面的话,则满足nums[l] < nums[mid],这个时候需要判断target和nums[mid]的关系,如果它在nums[l]和nums[mid]之间,则将搜索范围缩小到l, mid这里。所以需要将r = mid - 1。否则如果不是这种情况的话,则它肯定在mid + 1, r这个范围。那么就设置 l = mid + 1。
如果mid落在后面那个递增段呢,也类似,判断nums[l] > nums[mid]。这个时候就看target是否在mid + 1和r之间,是的话l = mid + 1,否则 r = mid - 1。
还有一种情况就是因为问题里提到的有相同的元素,这个时候我们就需要将l向mid的方向移动一位,来逐步逼近缩小搜索范围。
详细的代码实现如下:
public class Solution { public boolean search(int[] nums, int target) { int l = 0, r = nums.length - 1; while(l <= r) { int mid = (l + r) / 2; if(nums[mid] == target) return true; if(nums[l] < nums[mid]) { if(target >= nums[l] && target <= nums[mid]) r = mid - 1; else l = mid + 1; } else if(nums[l] > nums[mid]) { if(target >= nums[mid] && target <= nums[r]) l = mid + 1; else r = mid - 1; } else l++; } return false; } }
这个问题的时间复杂度也就是标准二分搜索的时间复杂度,为O(logN)。
相关推荐
leetcode 分类 :person_running::person_running::person_running: 算法 :person_running::person_running::person_running: 实践&理论 :books: :ear: :television: Binary Search(二分查找) easy 69: 278: 35: ...
leetcode LeetCode 这个库用于总结leetcode中遇到的习题 常用数据结构习题总结 1.线性表 解决进度 No. Describition mark 1 Remove Duplicates from Sorted Array 2 Remove Duplicates from Sorted Array II 3 ...
leetcode 1004 leetcode E:简单,M:中等,H:困难 数组和字符串 217. Contains Duplicate (E) 48. Rotate Image (M) -> 2 73. Set Matrix Zeroes (M) 1. Two Sum (E) 167. Two Sum II - Input array is sorted (E)...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
leetcode Coding-Interview A repo for popular coding interview problems mainly from Leetcode. 二分搜索/有序数组旋转 Find Minimum In Rotated Sorted Array Find Minimum In Rotated Sorted Array II Search ...
leetcode切割分组 leetcode 加减乘除运算 ...033_search_in_rotated_sorted_array.py # 旋转排序的数列中查找 034_find_first_and_last_position_of_element_in_sorted_array.py # 查找第一次出现和
in Rotated Sorted Array II/Solution.java) 2014/10/20 难的 [Java](./src/在旋转排序数组中查找最小值/Solution.java) 2014/10/15 中等的 [Java](./src/最大乘积子阵列/Solution.java) 2014/9/23 中等的 [Java](./...
Search in Rotated Sorted Array(搜索旋转排序数组)#数组 2020/12/08 19. Remove Nth Node From End of List(删除链表的倒数第N个节点) 153. Find Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值...
Search in Rotated Sorted Array II Search a 2D Matrix Search a 2D Matrix II Find Minimum in Rotated Sorted Array Find Minimum in Rotated Sorted Array II Median of Two Sorted Arrays H-Index II 暴力枚举...
leetcode添加元素使和等于 leetcode_py Python version of leetcode problems 33 Search in Rotated Sorted Array 问题:找到经过旋转的有序数组中是否有目标的数。 解法:基于二分的方法,根据 target、num[0]、...
问题/search-in-rotated-sorted-array.py 中等的 39 问题/组合-sum.py 中等的 40 问题/组合-sum-ii.py 中等的 49 问题/组字谜.py 中等的 50 问题/powx-n.py 中等的 53 问题/最大子数组.py 简单的 55 问题/跳转游戏....
leetcode 316 leetcode 题解更新脚本 用于快速的更新题解、同步leetcode的做题情况。 题解见: 文件名 用途 add_to_blog_solution_table.py 添加题解地址or题解语言到表格,能同步leetcode新题情况 blog_solution_...
Find Minimum in Rotated Sorted Array viii. Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. ...
颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...
leetcode 2 sum c Leetcode 练习记录 这个专案主要存放我练习Leetcode有针对难度分类的集合题库(Collection Question) 准备方式 分析tag的热门标签,熟悉各个标签解题的思路(解决该标签全部的easy和medium为主),再...
Search in Rotated Sorted Array74. Search a 2D Matrix I240. Search a 2D Matrix II2. Add Two Numbers50. Pow(x, n)34. First & LastPositionElementInSortedArr94. Binary Tree Inorder Traversal144. Binary ...
Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
简单编程: (分析,控制语句)排序 & 查找:二分查找:二分查找进阶:二分查找应用:二分查找应用:二分查找变种:二分查找变种:http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/简单数学:...
leetcode lintcode差异 leetcode-python 九章算法基础班 二分 题目 地址 153. Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two ...
search-in-rotated-sorted-array ,比较中间值和边,而不是目标和边 40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符