LeetCode 81. 搜索旋转排序数组 II【二分查找】
发布日期:2021-06-29 14:32:19
浏览次数:3
分类:技术文章
本文共 1197 字,大约阅读时间需要 3 分钟。
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true 示例 2:输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false解题思路
本题是需要使用二分查找,怎么分是关键,举个例子:
第一类
10111 和 11101 这种。此种情况下 nums[start] == nums[mid],分不清到底是前面有序还是后面有序,此时 start++ 即可。相当于去掉一个重复的干扰项。 第二类 2 3 4 5 6 7 1 这种,也就是 nums[start] < nums[mid]。此例子中就是 2 < 5; 这种情况下,前半部分有序。因此如果 nums[start] <=target<nums[mid],则在前半部分找,否则去后半部分找。 第三类 6 7 1 2 3 4 5 这种,也就是 nums[start] > nums[mid]。此例子中就是 6 > 2; 这种情况下,后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找,否则去前半部分找。AC
class Solution { public: bool search(vector & nums, int target) { int left=0,right=nums.size()-1; while(left<=right){ int mid = (left+right)/2; if(nums[mid] == target) return true; if(nums[left] == nums[mid]) left++; else if(nums[mid]<=nums[right]){ if(target>nums[mid] && target<=nums[right]){ left=mid+1; }else{ right=mid-1; } }else{ if(target>=nums[left] && target
转载地址:https://chocolate.blog.csdn.net/article/details/106210792 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月07日 11时10分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
基于nuxt下asyncData,fetch发送axios请求(四)
2019-04-29
插件机制+自定义axios(五)
2019-04-29
Redis的学习之路
2019-04-29
Windows下Redies+GUI安装,使用Jedis与spring boot 整合
2019-04-29
Windows创建本地版本库(1)
2019-04-29
基于java的酒店管理系统的设计与实现
2019-04-29
基于WEB的仓库管理系统的设计与实现
2019-04-29
基于java的web聊天系统
2019-04-29
基于java的俄罗斯方块的设计与实现
2019-04-29
基于java的魂斗罗的设计
2019-04-29
基于java的网页内容管理
2019-04-29
基于java的学生管理系统
2019-04-29
基于java网盘搜索的设计与实现
2019-04-29
基于SSM的仿小米商城源码
2019-04-29
基于SSM的医院人事管理系统的设计与实现
2019-04-29
基于SSM框架的超市管理系统
2019-04-29
基于java的SSM框架理财管理系统的设计与实现
2019-04-29
基于java的图书管理系统的设计与实现
2019-04-29
基于SSM的兼职论坛系统的设计与实现
2019-04-29