Arrays.binarySearch

        今天在开发时，要判断一个逗号分隔的字符串中是否包含指定的字符串，考虑到aaa,aaa10,aaa11这种字符串无法正确判断aaa是否存在。因此先将调String的split方法将其转换成字符串数组。然后再用for循环或ArrayUtils.contains判断即可，后来在使用时发现Array.binarySearch(arr,obj)方法，虽然二分法查找需要被查找的数组已经是排好序的，但每次将查找范围缩小一半，元素比较的效率大大提高。特别越往后，二分法的耗时基本不变，而用contains()比较的耗时越来越大。

一.public static int binarySearch(int[] a, int key)说明

        使用二进制搜索算法来搜索指定的 int 型数组，以获得指定的值。

        必须在进行此调用之前对数组进行排序（通过上面的 sort 方法）。如果没有对数组进行排序，则结果是不明确的。
        如果数组包含多个带有指定值的元素，则无法保证找到的是哪一个。   
        参数： a - 要搜索的数组。 key - 要搜索的值。 
        返回： 搜索键的索引，如果它包含在列表中；否则返回 (-(插入点) - 1)。
        插入点被定义为将键插入列表的那一点：即第一个大于此键的元素索引，如果列表中的所有元素都小于指定的键，则为 list.size()。
        注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。 另请参见： sort(int[]) 

 

二.实例说明如果没有对数组进行排序，则结果是不明确的

        字符串“218”在字符串“2180,2180,218,2180,21820,2180,2181,217”中，但如果没有对数组进行排序，其返回-1，表明未包含在列表中。

import java.util.Arrays;

public class BinarySearchTest {

    public static void main(String[] args) {
        
        String code = "218";
        String str = "2180,2180,218,2180,21820,2180,2181,217";
        String[] dArray = str.split(",");
        int res = Arrays.binarySearch(dArray, code);
        System.out.println(res);
    }
}

        运行结果：-1

        而经过Arrays.sort(dArray)排序后，结果运行正确。

import java.util.Arrays;

public class BinarySearchTest {

    public static void main(String[] args) {
        
        String code = "218";
        String str = "2180,2180,218,2180,21820,2180,2181,217";
        String[] dArray = str.split(",");
        Arrays.sort(dArray);
        int res = Arrays.binarySearch(dArray, code);
        System.out.println(res);
    }
}

        运行结果：1

 

三.比较测试一下Arrays.binarySearch、list.contains两种方法的效率差异

package com.bijian.study;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class EffCompare {

	public static void main(String[] args) {
		
	    List list = new ArrayList(10000);  
	     for(int i=0;i<100000;i++){  
	       list.add("jack"+i);  
	     }  
	     String[] array = (String[]) list.toArray(new String[10000]);  
	     Arrays.sort(array);  
	     long begin = System.currentTimeMillis();  
	     for(int k=60000;k<70000;k++){  //1  
	       int index = Arrays.binarySearch(array, "jack"+k);  
	       //System.out.println(Arrays.binarySearch(array, "jack"+k));  
	     }  
	     long end = System.currentTimeMillis();  
	     System.out.println("二分法查找10000个item消耗："+(end-begin)+"毫秒");  
	       
	     begin = System.currentTimeMillis();  
	     for(int n=60000;n<70000;n++){  //2  
	       boolean iist = list.contains("jack"+n);  
	       //System.out.println(list.contains("jack"+n));  
	     }  
	     end = System.currentTimeMillis();  
	     System.out.println("contains查找10000个item消耗："+(end-begin)+"毫秒");  
	  }
}

        运行结果：

二分法查找10000个item消耗：8毫秒
contains查找10000个item消耗：14174毫秒

        测试的时候可以将 1,2 处的代码改为for(int n=0;n<10000;n++){，for(int n=90000;n<100000;n++){，可以发现，起始值越往后，二分法的耗时基本不变，而用contains()比较的耗时越来越大，原因当然是contains方法进行了越来越多的equals()调用（需要不断的调用equals()方法来比较这个对象和String[]中或List中的元素对象是否相等）。

 

参考文章：http://blog.chinaunix.net/uid-11898547-id-3220732.html