偶然在博客中见对百度一个面试题的探讨,写些自己的看法以及指出探讨中不对的观点:百度面试题:求绝对值最小的数 有一个已经排序的数组(升序),数组中可能有正数、负数或0,求数组中元素的绝对值最小的数,要求,不能用顺序比较的方法(复杂度需要小于O(n)),可以使用任何语言实现 例如,数组{-20,-13,-4, 6, 77,200} ,绝对值最小的是-4。

  今天申请了博客园账号,在下班后阅览博客时发现了一个关于百度面试题探讨的博客(其实是个很基础的问题),此博客url为:http://www.blogjava.net/nokiaguy/archive/2013/01/30/394920.html

  其中下面有人评论为:

    有序列表查找显然二分啊,博主貌似对java的arrays和collections不是很熟。
    private static int getMinAbsoluteValue(final int[] source) {
      int index = Arrays.binarySearch(source, 0);
      int insertPos = -1 - index;
      return index >= 0 ? 0
        : source[insertPos == source.length ? source.length - 1
        : insertPos];
    }

  那我接下来谈下我的看法。刚开始看到这个问题的时候发现不能用顺序比较的方法,那我觉得可能要写一段很长的方法,后来发现评论区有人写了上边的方法,所以只能说我对Arrays的binarySearch(*,key)方法也不熟悉!!!于是我查了下API:

***********************API内容**********************

binarySearch

public static int binarySearch(int[] a,
                               int key)
使用二分搜索法来搜索指定的 int 型数组,以获得指定的值。必须在进行此调用之前对数组进行排序(通过 sort(int[]) 方法)。如果没有对数组进行排序,则结果是不确定的。如果数组包含多个带有指定值的元素,则无法保证找到的是哪一个。
参数:
a - 要搜索的数组
key - 要搜索的值
返回:
如果它包含在数组中,则返回搜索键的索引;否则返回 (-(插入点) - 1)插入点 被定义为将键插入数组的那一点:即第一个大于此键的元素索引,如果数组中的所有元素都小于指定的键,则为 a.length。注意,这保证了当且仅当此键被找到时,返回的值将 >= 0。

***********************API内容**********************

  发现此方法是使用二分来搜索指定key值所在的索引(此方法要求*数组必须是排序过得数组没不然结果会不对,一下分析都是针对*升序后的分析),如果*中不存在key则返回(-(插入点) - 1,这个插入点是指排序过得数组*中大于key的后一个值的索引(此处还是比较难理解的,我是通过debug后才理解的,因为-1所以返回值为该值后第二个数的索引;如果数组中所有数都小于key则返回*.length),不得不说评论的那位老哥知识面还是挺广的,可是我运行了下老哥的那个demo,发现结果并不对,我也找到了其不对的原因,如下为我写的正确的demo(已验证)如下:

@org.junit.Test

public void listTest(){

  int[] sourcenum = new int[]{6,23,4,1,-2,-8};

  Arrays.sort(sourcenum);

  int min = getMinAbsoluteValue(sourcenum);

  System.out.println(min);

}

private static int getMinAbsoluteValue(final int[] source) {

  int index = Arrays.binarySearch(source, 0);

  //未找到情况下

  int insertFront = 0-index-2;//找到0的前一个数的索引

  int insertNext = 0-index-1;//找到的后一个数的索引

  return index == index > 0 ? source[index == source.length ? source.length-1 : index]//找到0的情况下载数组中通过0的索引取数

      : Math.abs(source[insertFront]) > Math.abs(source[insertNext]) ? source[insertNext] : source[insertFront];//未找到的情况下对0前后的那个数进行绝对值对比

}

 

Wait for the flying eagles Believe that I will succee and just stack to it_Mr.Liu
原文地址:https://www.cnblogs.com/liu-eagles/p/7801069.html