【剑指offer-Java版】08旋转数组的最小数字

系统管理员 2022-08-21 08:53 20阅读 0赞

旋转数组最小数字：暴力方法就是遍历-有效的方法是二分，但是存在失效的情况  
几个特别的测试用例需要注意下：  
数组中含有多个相同的数字  
最小数字就是第一个

public class _Q08 {
    
        public int MinInReverse(int array[]){
            if(array == null || array.length == 0) return Integer.MIN_VALUE;
    
            if(array.length == 1) return array[0];
    
            int indexL = 0, indexR = array.length - 1, indexMid = array.length/2;
    
            while (indexL < indexR) {
                if ((array[indexL] < array[indexMid]) && (array[indexR] < array[indexMid])) {
                    indexL = indexMid;
                    indexMid = (indexL + indexR) / 2;
                } else if ((array[indexL] > array[indexMid]) && (array[indexR] > array[indexMid])) {
                    indexR = indexMid;
                    indexMid = (indexL + indexR) / 2;
                } else if ((array[indexMid] == array[indexL]) || (array[indexMid] == array[indexR])) {
                    return Min(array);
                } else if (array[indexL] < array[indexR]) {
                    return array[0];
                }
            }
            return Integer.MAX_VALUE;
        }
    
        public int Min(int array[]){
            int min = Integer.MAX_VALUE;
    
            for(int i=0; i<array.length; i++){
                if(array[i] < min) min = array[i];
            }
    
            return min;
        }
        }

测试代码：

public class _Q08Test extends TestCase {
        
    
        _Q08 minInReverse = new _Q08();
    
        public void testMinInReverse() throws Exception{
    
            int array1[] = {
       1,1,1,0,1};
            int array2[] = {
       3,4,5,1,2};
            int array3[] = {
       1,2,3,4,5};
            int array4[] = {
       1};
            int array5[] = null;
    
            int min = minInReverse.MinInReverse(array5);
            System.out.println("min = " + min);
        }
        }