JavaScript#33:数组--(搜索旋转排序)Search in Rotated Sorted Array(MIDDLE)

分析一:

给定一个循环无重复有序数组,如12345 ->34512​,查找给定数值target在数组中的下标,如没有则返回-1。

循环递增数组有这么一个性质:以数组中间元素将循环递增数组划分为两部分,则一部分为一个严格递增数组,而另一部分为一个更小的循环递增数组。

当中间元素大于首元素时,前半部分为严格递增数组,后半部分为循环递增数组;当中间元素小于首元素时,前半部分为循环递增数组;后半部分为严格递增数组。

分析二:

对于一个数组4,5,6,7,0,1,2 你首先找到那个转折点,就是大于下一个相邻数字的那个数字的下标,在这个数组就是数字7的下标3。

步骤:

1 找到转折点下标,把数组分成两个有序的子数组

2 如果转折点下标返回-1,意思是数组有序,可以直接在整个数组中查找

3返回不是-1,数组是旋转后的数组。 如果target大于等于第一个元素即A[0],那就在左半部分数组中查找,如果target小于A[0],那就在右半部分中寻找

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 数组在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称...
    朱森阅读 4,331评论 2 13
  • 冒泡排序 冒泡排序相对来说是较为简单的一种排序,它的思想就是在每一次循环中比较相邻的两个数,通过交换的方式,将最小...
    陌上疏影凉阅读 672评论 0 3
  • 旋转数组的最小数字 题目 给定一个递增的旋转数组A,返回旋转数组中的最小值。旋转数组:给定一个已排序的数组,假设为...
    蓝雪冬荷阅读 538评论 0 0
  • 我想大家对于挣钱都是感兴趣的吧?!可是怎样才能实现财务自由呢?我想提供几点小建议希望对大家有帮助。 1.创业中最重...
    香水有毒_622阅读 284评论 0 0
  • 欧思曼头层牛皮双肩包女真皮百搭包包女包休闲女士韩版双肩背包女 价格:356.00-398.00 元 2016新款双...
    骑驴的马小马阅读 234评论 0 0

友情链接更多精彩内容