折半查找部分有序

部分有序 本周qq群有人咨询

Search in Rotated Sorted Array 来源: https://leetcode.com/problems/search-in-rotated-sorted-array/ 难度:Difficulty: Hard

题目

Suppose a sorted array is rotated(旋转的) at some pivot unknown to you beforehand(提前的) eg: 0 1 2 3 4 5 6 7 旋转3个might become 4 5 6 7 0 1 2 3. You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array.

分析:

观察:

  • 举例就用0-9来打比方很容易观察规律
  • 7为旋转点两边都是升序 【4 5 6】 【0 1 2 3 】这个问题来了 不清楚应该去那边去寻找方向了 例如寻找3 可能在left 也有可能在right 从7 来看 一个升序 一个降序 都可能 …….. ……. 从这个思路无法判断,你明确表示出来 判断不了,你感觉没问题就是分析不出来呀 然后果断在换个思路 这个我一般不具备 不能在这里死磕 不然陷入了题目给造成的陷阱去了

Q1 有序数组折半是中间位置和查找元素 现在中间位置可以判断出来 查找元素元素方向无法判断如果不匹配是 去left 还是right寻找

我感觉还是判断趋势 假如array[begin end] case 1 0 1 2 3 4 5 6 7 特点:7>0 array[end] > array[begin]升序

case 2 4 5 6 7 0 1 2 3 特点:array[end] < array[begin] 旋转点在中间

是升序 还是降序还是 还是混合都有 我用的根据相 邻2个元素 6 7 0 判断出来了还是解决无法判断呢

Q2一个数组 确定中间位置去判断(相邻元素) 假如是7 left是 升序[4 5 6 7] 你如何判断查找元素3位置 回到问题Q1了 你忘记是有序了 一眼看出3不再这里面呀 3<4<7 回到问题Q1了 A2:为什么那相邻元素呢 为什么不用 array[end],array[begin] 一个数组假如有拐点 无法判断就不去判断了,继续拆分

如果一个数组不满足判断条件 继续拆分 满足到符合条件为止

步骤

step 1 选择中间位置 此时 数组将一份为二 A,B 一边是完全有序 部分A 一是包含旋转点部分B step 2 完全有序 部分A 查找非常简单 判断查找数据是否在有序数组A中 如果在A中对范围A进行查找 step 3 如果没有A中 对B重复步骤 1 2

coding

class Solution { public: int search(vector& nums, int target) { int begin=0;//开始位置 int end=nums.size()-1;//结束位置

1.   //如果元素个数小于<<2个不适合2.   if(0 ==end )3.   {4.       return target ==nums[0]?0:-1;5.   }6.   if(1 == end )7.   {8.       if(target ==nums[0] ) {return 0;}9.       if(target ==nums[1]) {return 1;}10.       return -1;11.   }12.   while(begin<=end)13.   {    14.        int mid=(end+begin)/2;15.       //find 16.       if( target == nums[mid])17.       {18.           return mid;19.       }20.21.       // 完全有序A |mdi|包含拐点的有序B22.       if(nums[begin]<=nums[mid] )23.       {    //查找数据在完全有序数组A中 只要对数组A进行折半查找24.           if(nums[begin]<=target && target <nums[mid] )25.           {26.               end=mid-1;27.           }else //包含拐点的有序B中28.           {29.               begin=mid+1;30.           }31.       }else32.       { // 包含拐点的有序B|mdi|完全有序A33.34.            if(nums[mid]<target && target <=nums[end] )35.           {36.               begin=mid+1;37.           }else //包含拐点的有序B中38.           {39.              end=mid-1;40.           }41.       }42.   }43.44.   return -1;//not find 45.}

};

验证:

代码错误 <= 写成 << 不是比较运算符了 if(nums[begin]<<target && target<nums[mid] ) 改为 nums[begin]<=target

[5,1] 最后两个元素分隔时候 if(nums[begin]<nums[mid] ) 改为 if(nums[begin]<=nums[mid] )

难点:

当中间元素和查找元素不相等时候 如何确定查找元素范围 ->通过通过比较中间元素 和开始和结束位置 确定完全有序范围 -> 从而推断查找元素范围

原文发布于微信公众号 - 架构说(JiaGouS)

原文发表时间:2016-05-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

[每日一题]偶数求和

题目描述 有一个长度为n(n<=100)的数列,该数列定义为从2开始的递增有序偶数(公差为2的等差数列),现在要求你按照顺序每m个数求出一个平均值,如果最后不足...

30850
来自专栏专注数据中心高性能网络技术研发

[LeetCode]HashTable主题系列{第3题}

1. 内容介绍 开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解...

38490
来自专栏七夜安全博客

从多项式相加看线性结构

14530
来自专栏章鱼的慢慢技术路

C语言简明数据类型指南

20770
来自专栏大数据文摘

正则表达式太慢?这里有一个提速100倍的方案(附代码)

28940
来自专栏追不上乌龟的兔子

[多少懂点位运算]找出唯一的数字

大家都知道现代计算机的底层是以二进制为基础的,计算机所有的操作最后都归结到了简单的二进制位运算上:与,或,非和异或。

27750
来自专栏算法channel

动态规划:括号知多少

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

37770
来自专栏chenjx85的技术专栏

leetcode-258-Add Digits

22340
来自专栏算法channel

机器学习|快速排序思想求topk

01 — Topk by quicksort 问题是求出数据集中,按照某个规则定义的元素大小,取前k个元素。 为了简化起见,直接求数值型数组的前k个最大元素。...

59780
来自专栏编程直播室

读书笔记:《算法图解》第三章 递归

17550

扫码关注云+社区

领取腾讯云代金券