LeetCode 81. 搜索旋转排序数组 II【二分查找】
发布日期:2021-06-29 14:32:19
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月03日 15时57分56秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
知乎:学计算机的女生都怎么样了?
2019-04-29
华为重磅反击,鸿蒙来了!
2019-04-29
常用电子接口大全,遇到不认识的,就翻出来对照辨认!
2019-04-29
芯片IC附近为啥要放0.1uF的电容?
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录。
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录(上)
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录(下)
2019-04-29
突破!台积电1nm芯片,有了新进展。
2019-04-29
一文读懂全系列树莓派!
2019-04-29
自制一个害羞的口罩,见人就闭嘴,戴着可以喝奶茶
2019-04-29
聊聊我是如何编程入门的
2019-04-29
J-Link该如何升级固件?
2019-04-29
485通信自动收发电路,历史上最详细的解释
2019-04-29
【视觉盛宴三】不好意思,这些线材接口的横截面真的没见过
2019-04-29
一位头发发白的神人教你怎么写程序,运维,买电脑,写文章,平面设计!
2019-04-29
【第二期】那些设计漂亮、有创意的电路板!
2019-04-29
【第三期】那些设计漂亮、有创意的电路板!
2019-04-29
继续推荐公众号~
2019-04-29
「第二篇」全国一等奖,经验帖。
2019-04-29
「第三篇」全国电子设计竞赛,这些你必须知道的比赛细节,文末附上近十年电赛题目下载...
2019-04-29