百度面试题：求绝对值最小的数

1、

    有一个已经排序的数组（升序），数组中可能有正数、负数或0，求数组中元素的绝对值最小的数，要求，不能用顺序比较的方法（复杂度需要小于O（n）），可以使用任何语言实现

例如，数组{-20，-13，-4, 6, 77,200} ，绝对值最小的是-4。

 

    算法实现的基本思路

找到负数和正数的分界点，如果正好是0就是它了，如果是正数，再和左面相邻的负数绝对值比较，如果是负数，取取绝对值与右面正数比较。还要考虑数组只有正数或负数的情况。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;


public class MinAbsoluteValue {

	//http://www.blogjava.net/nokiaguy/archive/2013/01/30/394920.html 方法
	/**
	 * 三种情况：
	 * 1、有正负数
	 * 2、只有正数
	 * 3、只有负数
	 * 
	 * 找到正负数临界点，比较绝对值大小即可
	 */
	private static int getMinAbsoluteValue(int[] source)
    {
         
        int index = 0;
        int result = 0; 
        int startIndex = 0;
        int endIndex = source.length - 1;
        //  计算负数和正数分界点
        while(true)
        {                //  计算当前的索引
            index = startIndex + (endIndex - startIndex) / 2;
            int s = (endIndex - startIndex)/2;
            
            result = source[index];                //  如果等于0，就直接返回了，0肯定是绝对值最小的
            if(result==0)
            {
                return 0;
            }               //  如果值大于0，处理当前位置左侧区域，因为负数肯定在左侧
            else if(result > 0)
            {
                if(index == 0)
                {
                    break;
                }
                if(source[index-1] >0)
                    endIndex = index - 1;
                else if(source[index-1] ==0)
                    return 0;
                else
                    break;
            }            //  如果小于0，处理当前位置右侧的区域，因为正数肯定在右侧的位置
            else
            {
                if(index == endIndex)
                    break;
                if(source[index + 1] < 0)
                    startIndex = index + 1;
                else if(source[index + 1] == 0)
                    return 0;
                else
                    break;
            }
        }
        //  根据分界点计算绝对值最小的数
        if(source[index] > 0)
        {
            if(index == 0 || source[index] < Math.abs(source[index-1]))
                result= source[index];
            else
                result = source[index-1];
        }
        else
        {
            if(index == source.length - 1 || Math.abs(source[index]) < source[index+1])
                result= source[index];
            else
                result = source[index+1];
        }
         
         
        return result;
    }
	
	
    public static void main(String[] args) throws Exception
    {
         
        int[] arr1 = new int[]{-23,-22,-3,-2,1,2,3,5,20,120};
        int[] arr2 = new int[]{-23,-22,-12,-6,-4};
        int[] arr3 = new int[]{16,22,33,55,66,333};
        int value = getMinAbsoluteValue(arr1);
        System.out.println(value);
        value = getMinAbsoluteValue(arr2);
        System.out.println(value);
        value = getMinAbsoluteValue(arr3);
        System.out.println(value);
        
        System.out.println("---------------------------");
        //自己方法
        int value2 = getAbsValue(arr1);
        System.out.println(value2);
        value2 = getAbsValue(arr2);
        System.out.println(value2);
        value2 = getAbsValue(arr3);
        System.out.println(value2);
    }
    
    
    //自己方法
    public static int getAbsValue(int[] array){
    	if(array == null || array.length == 0) return 0;
    	Map sortMap = new HashMap();
    	int [] tmpArray = new int[array.length];
    	for(int i = 0;i<array.length;i++){
    		int element = array[i];
    		sortMap.put( Math.abs(element),element);
    		tmpArray[i] = Math.abs(element);
    	}
    	
    	Arrays.sort(tmpArray);
    	return Integer.parseInt(sortMap.get(tmpArray[0]).toString());	   	
    } 

}

 

 

 

。