欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Arrays.binarySearch 博客分类: java基础 ArraysbinarySearch 

程序员文章站 2024-02-25 18:08:27
...

        今天在开发时,要判断一个逗号分隔的字符串中是否包含指定的字符串,考虑到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中的元素对象是否相等)。
 
相关标签: Arrays binarySearch