旋转数组（采用二分查找的方法来查找出数组中的最小值，注意特殊情况）

清疚 2021-09-30 15:42 162阅读 0赞

int MinInOrder(int\* numbers,int index1,int index2)\{ //由于中间的数字和前面后面的数字都相同因此只能采用顺序查询

int result = numbers\[index1\];  
for(int i=index1;i<=index2;i++)\{  
if(result>numbers\[i\])  
result=numbers\[i\];  
\}  
return result;  
\}  
int Min(int\* numbers,int length)\{  
if(numbers==nullptr&&length==0)\{  
logic\_error ex("Invalid parameters");  
throw new exception (ex);  
\}  
int index1 =0;  
int index2= length-1;  
int midindex =index1;  
while(numbers\[index1\]>=numbers\[index2\])\{    
if(index2-index1==1)  //当前后指针之间的距离为1时，此时找到了最小的数，即后面的指针指向的数，第一个指向的是最大的数  
\{  
midindex = index2;  
break;  
\}  
midindex=(index1+index2)/2;  
if(numbers\[index1\]==numbers\[midindex\]&&numbers\[index2\]==numbers\[midindex\])  
return MinInOrder(numbers,index1,index2);  
if(numbers\[midindex\]>=numbers\[index1\])\{  //如果中间的数字比第一个大，证明中间的数在第一个递增数列中因此把头指针指向中间  
index1=midindex;  
\}  
else if(numbers\[midindex\]<=numbers\[index2\])//如果中间的数字比最后一个数小证明在后面的递增数列中，因此把后面的指针指向中间  
index2=midindex;  
\}  
return numbers\[midindex\];  
\}

转载于:https://www.cnblogs.com/XiaoXiaMi123/p/8644778.html

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|二分查找No.6】leetcode 153. 寻找旋转排序数组中的最小值

【算法|二分查找No.6】leetcode 153. 寻找旋转排序数组中的最小值

àì夳堔傛蜴生んèń/ 2024年04月27日 07:01/ 0 赞/ 27 阅读

相关有序数组中的二分查找

分查找又叫折半查找，要求数组/序列满足一定的有序性，根据某些判断条件不断缩小查找的范围。因为每次范围缩小为原来的一半，所以叫二分或者折半。如此说来，问题就在于： ...

朱雀/ 2024年04月17日 05:32/ 0 赞/ 35 阅读

相关 leetcode 153.寻找旋转排序数组中的最小值（Java 二分查找 medium）

[https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/][https_leetcode-

桃扇骨/ 2023年08月17日 17:01/ 0 赞/ 98 阅读

相关 LeetCode153. 寻找旋转排序数组中的最小值【二分查找】

难度：`中等` 题目描述： > 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。 > 例如，原数组 nums =\[0,1,

电玩女神/ 2022年11月17日 03:50/ 0 赞/ 157 阅读

相关 198-旋转数组中的查找

题目如下：假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )

分手后的思念是犯贱/ 2022年10月30日 10:22/ 0 赞/ 108 阅读

相关 197-找出旋转数组中的最小值

题目如下：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 \[3,4,5,1,2\

逃离我推掉我的手/ 2022年10月30日 10:20/ 0 赞/ 158 阅读

相关 LeetCode 搜索旋转排序数组【二分查找】

1 二分查找整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）

短命女/ 2022年09月12日 06:54/ 0 赞/ 125 阅读

相关二分查找思想寻找有序数组中查找最小值

思想：循环有序数组最大的特点是利用二分查找时，有一边总是有序的，利用这个特点，利用value存储历史最小值当左边有序，则用A\[low\]与value比较即可得出当前左边的

左手的ㄟ右手/ 2022年08月12日 01:15/ 0 赞/ 130 阅读

相关旋转数组查找指定值

递增数组\[1,2,3,4,5\]，变化为\[5,6,1,2,3,4\]，给定K，判断是否存在，并返回其索引位置二分查找选择中间位置作为判断的分界点所以二分

男娘i/ 2022年05月12日 04:04/ 0 赞/ 127 阅读

相关旋转数组（采用二分查找的方法来查找出数组中的最小值，注意特殊情况）

int MinInOrder(int\ numbers,int index1,int index2)\{ //由于中间的数字和前面后面的数字都相同因此只能采用顺序查询 int

清疚/ 2021年09月30日 15:42/ 0 赞/ 163 阅读