摘要：如此，便可以缩小搜索范围，提高时间复杂度，最终第一个指针指向前面子数组的最后一个元素，而第二个指针指向后面子数组的第一个元素，它们处于相邻位置，而第二个指针指向的刚好是最小的元素。
旋转数组的最小数字（二分查找）
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：
1.设置两个指针，初始状态第一个指针指向前面子数组的第一个元素，第二个指针指向后面子数组的最后一个元素；
2.找到两个指针的中间元素；
3.若其大于等于第一个指针指向的元素，则说明其在前面的子数组中，且显然最小元素在中间元素的右边，若其小于等于第二个指针指向的元素，则说明其在后面的子数组中，且显然最小元素在中间元素的左边。
如此，便可以缩小搜索范围，提高时间复杂度，最终第一个指针指向前面子数组的最后一个元素，而第二个指针指向后面子数组的第一个元素，它们处于相邻位置，而第二个指针指向的刚好是最小的元素。
注意：按旋转规则，第一个元素应该是大于或等于最后一个元素的；但也有特例：若把排序数组的前0个元素搬到最后面，及排序数组本身，仍是数组的一个旋转，此时数组中的第一个数字是最小的数字。
注意：当两个指针指向的数字及它们中间的数字三者相等时，无法判断中间数字位于前面的子数组还是后面的子数组，也就无法移动两个指针来缩小查找的范围，此时只能用顺序查找的方法。
例如：数组{1,0,1,1,1}和数组{1,1,1,0,1}都可看成是递增数组{0,1,1,1,1}的旋转。第一种情况，中间数字位于后面的子数组，第二种情况，中间数字位于前面的子数组。
function minNumberInRotateArray(arr) {
let index1 = 0;
let index2 = arr.length - 1;
let indexMid = index1;
while(arr[index1] >= arr[index2]) {
if(index2 - index1 == 1) {
indexMid = index2;
break;
}
indexMid = Math.floor((index1 + index2 ) / 2);
//如果下标为index1、index2和indexMid指向的三个数字相等
//则只能顺序查找
if(arr[index1] == arr[index2] && arr[indexMid] == arr[index1]) {
return MininOrder(arr,index1,index2);
}
if(arr[indexMid] >= arr[index1]) {
index1 = indexMid;
}
if(arr[indexMid] <= arr[index2]) {
index2 = indexMid;
}
}
return arr[indexMid];
}
//按顺序查找函数
function MininOrder(arr,index1,index2) {
let res = arr[index1];
for (var i = index1 + 1; i <= index2; i++) {
if(res > arr[i]) {
res = arr[i];
}
}
return res;
}
console.log(minNumberInRotateArray([3,4,5,1,2]));
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/107504.html
摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 常见数据结构 简单数据结构（必须理解和掌握） 有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小） 无序数据结构：集合、字典、散列表，无序...
摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 常见数据结构 简单数据结构（必须理解和掌握） 有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小） 无序数据结构：集合、字典、散列表，无序...
摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 常见数据结构 简单数据结构（必须理解和掌握） 有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小） 无序数据结构：集合、字典、散列表，无序...
摘要：数据结构程序数据结构算法数据结构基本概念数据的逻辑结构反映数据元素之间的关系的数据元素集合的表示。这两部分信息组成数据元素的存储映象，称为结点。 本文涉及更多的是概念，代码部分请参考之前写过的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本数据结构和查找算法 本文主要是基础的数据结构和算法概念，可能部分地方会涉及更高级的算法和算法，具体内容以...
摘要：栈被称为一种后入先出的数据结构。散列使用的数据结构叫做散列表。这些操作需要求助于其他数据结构，比如下面介绍的二叉查找树。 前言 在过去的几年中，得益于Node.js的兴起，JavaScript越来越广泛地用于服务器端编程。鉴于JavaScript语言已经走出了浏览器，程序员发现他们需要更多传统语言（比如C++和Java）提供的工具。这些工具包括传统的数据结构（如链表，栈，队列，图等），...
摘要：通过两个二分查找的条件继续进行问题的分析，那么问题又来了，二分查找是快速的查找一个数据是否存在一组数据中，而且效率极高，亿查找一个数据只需次查找。二分查找的三点重点循环退出条件注意是而不是。 showImg(https://segmentfault.com/img/remote/1460000018761246);这篇文章主要深入数据结构与算法在解决实际问题怎么运用和分析的，对于 IP...
阅读 3456·2021-11-22 11:59
阅读 922·2021-09-27 13:36
阅读 3582·2021-09-24 09:47
阅读 2204·2021-09-01 11:39
阅读 954·2021-08-31 09:37
阅读 2247·2021-08-05 10:01
阅读 1642·2019-08-30 15:55
阅读 651·2019-08-30 15:54
