在数组中找到一个局部最小的位置

刺骨的言语ヽ痛彻心扉 2022-05-29 02:30 131阅读 0赞

![Center][]

//在数组中找到一个局部最小的位置
    public class MinArr{
    	
        //(1)获得局部最小的位置
        public static int GetMinArr(int[]arr)
        {
        	if(arr==null||arr.length==0)
        	{
        		return Integer.MIN_VALUE;
        	}
        	if(arr.length==1)
        	{
        		return arr[0];
        	}
        	if(arr[0]<arr[1])
        	{
        		return arr[0];
        	}
        	if(arr[arr.length-1]<arr[arr.length-2])
        	{
        		return arr[arr.length-1];
        	}
        	int re=0;
        	for(int i=1;i<arr.length-1;i++)
        	{
        		if(arr[i-1]>arr[i]&&arr[i]<arr[i+1])
        		{
        			re=arr[i];
        			break;
        		}
                 
        	}
        	return re;		
    
        }
        
        //(2)二分查找算法(时间复杂度O(logN),空间复杂度O(1))
        public static int GetMinArr2(int[]arr)
        {
        	if(arr==null||arr.length==0)
        	{
        		return -1;
        	}
        	if(arr.length==1)
        	{
        		return arr[0];
        	}
        	if(arr[0]<arr[1])
        	{
        		return arr[0];
        	}
        	if(arr[arr.length-1]<arr[arr.length-2])
        	{
        		return arr[arr.length-1];
        	}
        	int left=1;
        	int right=arr.length-2;
        	int mid=0;
        	while(left<right)
        	{
        		mid=(left+right)/2;
        		if(arr[mid]>arr[mid-1])
        		{
        			right=mid-1;
        		}else if(arr[mid]>arr[mid+1]){
                    left=mid+1;
        		}else{
        			 return arr[mid];
        		}
    
        	}
        	return arr[left];
        }
    	public static void main(String[]args)
    	{
    	   //System.out.println("Hello");
    		int[]arr1={1};
    		int[]arr2={4,3,5,7,9};
    		System.out.println(GetMinArr(arr1));
    		System.out.println(GetMinArr(arr2));
    		System.out.println(GetMinArr2(arr2));
    	}
    }

![Center 1][]

[Center]: /images/20220529/e3fe9b7dbd4e4cd088e7f17d55957614.png
[Center 1]: /images/20220529/417cb5f8f7904f739a1a78ecec6de8b4.png