查找排序数组的最小值(js)

正文共570个字,预计阅读时间5分钟。

题目

在由小到大已排序的未知数组中,以某个元素为支点旋转(好比将序列沿着前后顺序围成环移动)得到了一个数组,请找出该数组的最小值。比如倘若原数组(对我们而言,并不知道原数组是什么)为0,1,2,3,4,5,6,7,可能经过旋转后得到数组 3,4,5,6,7,0,1,2。请找出旋转后数组的最小值(假定数组中没有重复数字)。

答: Math.min(), 卒。。。

从旋转点分开的两段数组都是有序的,而且前面数组的值都要大于后边子数组的元素,所以要找的旋转后数组的最小值也就是两个有序数组的分界线。

记中间位置的元素arr[mid],开始元素arr[start],结尾元素arr[end].。如果arr[mid]>arr[start],则分界点必然在[mid, end];如果arr[mid]<arr[start],则分界点必然在[start, mid];循环往复。。。。

所以有点像数学中的夹逼准则,有两个指针分别从数组开头和结尾想目的地不断逼近,直到缩小的范围成为一个点,则是目标值。

 1function findMin(arr){
 2let start=0;
 3let end=arr.length-1;
 4while(start<end){
 5let mid=Math.floor((start+end)/2);
 6// 当end-start==1时,mid==start
 7if (arr[mid]>=arr[start]) {
 8    // 对于原本升序的数组,arr[mid]不可能是最小值
 9    start=mid+1
10}
11else {
12    // 对于原本升序的数组,此时arr[mid]有可能是最小值
13    end= mid
14}
15}
16return arr[start]
17}

题目本身并不难,但重要的是要找好边界条件,比如arr[mid]>=arr[start])还是>会对结果有什么影响?

原文链接:https://www.jianshu.com/p/80cfbe22f406

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2018-06-07

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 1 移动有序区的元素,效率不高,下面我们来介绍一种新的插入排序算法...

35640
来自专栏数据结构与算法

洛谷P3357 最长k可重线段集问题(费用流)

题目描述http://www.cnblogs.com/zwfymqz/p/8559566.html 给定平面 x-O-yx−O−y 上 nn 个开线段组成的集合...

41760
来自专栏SeanCheney的专栏

《Pandas Cookbook》第03章 数据分析入门1. 规划数据分析路线2. 改变数据类型,降低内存消耗3. 从最大中选择最小4. 通过排序选取每组的最大值5. 用sort_values复现nl

15820
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

30790
来自专栏蜉蝣禅修之道

算法考试填数字问题

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

蓝桥杯题库基础练习:进制转换

23140
来自专栏ACM算法日常

基础算法|4 简单选择排序

我们之前已经了解了三种基础算法,分别为二分查找算法,冒泡排序算法,以及直接插入排序算法。俗话说得好,温故而知新,所以现在就让我们简单回顾一下之前的三种算法吧。...

13930
来自专栏xiaoxi666的专栏

今日头条笔试题:“最小数字*区间和”的最大值【单调栈】

  利用单调栈,从前向后和从后向前分别遍历一遍数组,得到每个元素的左边界和右边界(边界的定义即为碰到比该元素更小的即停止),最后用每个元素乘以每个元素对应的区间...

39410
来自专栏简书专栏

Numpy入门2

标题中的英文首字母大写比较规范,但在python实际使用中均为小写。 2018年7月26日笔记

13730
来自专栏ACM算法日常

字符串的距离(动态规划) - leetcode 72

,因为在刷leetcode的动态规划专题。动态规划虽然定义很简单,但是对于复杂的动态规划题目,很多时候还是很棘手的。

8620

扫码关注云+社区

领取腾讯云代金券