前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >查找排序数组的最小值(js)

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

作者头像
用户1332428
发布2018-07-30 14:58:32
2.9K0
发布2018-07-30 14:58:32
举报
文章被收录于专栏:人工智能LeadAI

正文共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];循环往复。。。。

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

代码语言:javascript
复制
 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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-06-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 人工智能LeadAI 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档