在有序旋转数组中找到最小值
程序员文章站
2024-03-15 20:16:36
...
【题目】
有序数组arr可能经过一次旋转处理,也可能没有,且arr可能存在重复的数。例如,有序数组[1,2,3,4,5,6,7],可以旋转为[4,5,6,7,1,2,3]。
给定一个可能旋转过的有序数组arr,返回arr中最小值。
【代码】
public static void main(String[] args) {
System.out.println(getMin(new int[]{4,5,6,7,1,2,3}));//1
System.out.println(getMin1(new int[]{5,5,5,5,6,4,5}));//4
}
//在有序旋转数组中找到最小值
public static int getMin(int[] arr){
//挨个比较查找
if(arr==null||arr.length==0){
return -1;
}
int res=Integer.MAX_VALUE;
for(int i=0;i<arr.length-1;i++){
int temp=arr[i]<arr[i+1]?arr[i]:arr[i+1];
res=Math.min(res, temp);
}
return res;
}
public static int getMin1(int[] arr){
//二分查找
if(arr==null||arr.length==0){
return -1;
}
int low=0;
int high=arr.length-1;
int mid=0;
while(low<high){
if(low==high-1){
break;
}
if(arr[low]<arr[high]){//[1 2 3 4 5],1<5 没旋转
return arr[low];
}
mid=(low+high)/2;
if(arr[low]>arr[mid]){//[5 1 2 3 4],5>2
high=mid;
continue;
}
if(arr[mid]>arr[high]){//[3 4 5 1 2],5>2
low=mid;
continue;
}
//到了这一步,说明arr[low]=arr[mid]=arr[high]
while(low<mid){
if(arr[low]==arr[mid]){
low++;//从low到Mid,值全部一样,
}
else if(arr[low]<arr[mid]){//5 5 5 4 5,突然发现arr[i]<arr[low],i就是断点处
return arr[low];
}
else{//遍历到i位置,突然发现arr[i]>arr[mid],则断点在i...mid上,5 5 5 5 6 4 5
high=mid;//????
break;
}
}
}
return Math.min(arr[low], arr[high]);
}
【说明】
二分查找法还要好好消化啊….
上一篇: 数据结构 快速排序 在一个数组中找到两个数,使之和为x
下一篇: java基础笔记整理(一)
推荐阅读
-
C在一段有序数组中判断一个数是否在这个数组中(二分查找)
-
在有序旋转数组中找到最小值
-
C++将一个有序数组按顺序移动,在移动后的数组中查找一个数字
-
在有序旋转数组中找到最小值
-
数据结构 快速排序 在一个数组中找到两个数,使之和为x
-
在一个数组中找到几个数之和为某个数字
-
LeetCode题解(0039):在不重复数组中找到和为目标数的所有组合(Python)
-
最短无序连续子数组(在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。)
-
LeetCode题解(0040):在不重复数组中找到和为目标数的所有组合(每个数字只能用一次)(Python)
-
二分查找法查找旋转数组的最小值(Python)