使用不同方法查找数组中某个特定值，并计算时间（改正二分法查找错误和数组转化集合错误）

本文链接：https://blog.csdn.net/java_raylu/article/details/70184544

这里修正刚才写的代码，发现很多根本没找到。。。代码有很多问题，这里一个个修正并记录写来：

1. 使用二分法时一定要先排序

错误的写法：

public int search() {  
        return Arrays.binarySearch(arr, targetValue);  
    }

改正后写法：

	public int search() {
		//System.out.println("arrLength"+ arr.length);
		Arrays.sort(arr);
		return Arrays.binarySearch(arr, targetValue);
	}

2.数组转化为List错误: 要使用Integer[]，不要使用int[]

int[]数组使用Arrays.asList()时会有问题，会把整个数组转化为List的一个元素，并没有把数组内的内容变成一个个List元素
错误的写法：

int[] arr = new int[1000];

List list = Arrays.asList(arr); //这样写arr[]就会变成list的第一个元素了。。整个list.size()=1;不符合预期

改正后写法：

Integer[] arr = new Integer[10000];

List list = Arrays.asList(arr);//数组转化成List

Set set = new HashSet(Arrays.asList(arr));//数组转化成Set

根据改正后的代码重新计算哪种方式查找最快，数组比较短时建议Loop，遍历比较长的数组可以用List

1.当数组长度100时，Loop最快

使用Loop查找花费的时间为15360
使用Arrays.binarySearch()查找花费的时间为440319
使用UseList查找花费的时间为349013
使用UseSet查找花费的时间为257706
2.当数组长度1000时，Loop最快，List次之
使用Loop查找花费的时间为125867
使用Arrays.binarySearch()查找花费的时间为1839786
使用UseList查找花费的时间为235946
使用UseSet查找花费的时间为1150720

3.当数组长度10000时，Loop最快，List次之

执行第一次：

使用Loop查找花费的时间为463787
使用Arrays.binarySearch()查找花费的时间为9032957
使用UseList查找花费的时间为693333
使用UseSet查找花费的时间为5693011

执行第二次：

使用Loop查找花费的时间为191573
使用Arrays.binarySearch()查找花费的时间为15807140
使用UseList查找花费的时间为154027
使用UseSet查找花费的时间为4534185

4.当数组长度1000000时， List比较快且相对稳定

执行第一次：

使用Loop查找花费的时间为4186451
使用Arrays.binarySearch()查找花费的时间为629270345
使用UseList查找花费的时间为167680
使用UseSet查找花费的时间为86613297

执行第二次：

使用Loop查找花费的时间为5113171
使用Arrays.binarySearch()查找花费的时间为624438347
使用UseList查找花费的时间为18483192
使用UseSet查找花费的时间为89199322

贴上修正后的代码

测试主代码：

package test1;

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

//在数组中查找某个特定值，如何查找最快？测试看看。。
//如何在数组中找出某个特定值，并计算执行时间
public class TestQuery1 {
	public static void main(String[] args) {
		//定义一个含有10000个数字的数组
		//int[] arr = new int[10000];//此方式无法by单个数字存入List
		Integer[] arr = new Integer[1000000];
		
		for(int i = 0; i < arr.length; i++){
			arr[i] = (int) (Math.random()*100000000);
		}

		List list = Arrays.asList(arr);
		//假设查询数字666
		int targetValue = 666;
		
		//使用Loop查找时间
		UseLoop useLoop = new UseLoop(arr, targetValue);
		useLoop.spendTime("Loop");
		
		//使用Arrays.binarySearch()方法查询
		UseArraysBinary  useAB = new UseArraysBinary(arr, targetValue);
		useAB.spendTime("Arrays.binarySearch()");

		//使用集合List查询
		UseList useList = new UseList(arr, targetValue);
		useList.spendTime("UseList");
		
		//使用集合set查询
		UseSet useSet = new UseSet(arr, targetValue);
		useSet.spendTime("UseSet");
	}
}

计算时间代码，搞成抽象类了

package test1;

public abstract class SpendTime {
	
	protected Integer[] arr;
	protected int targetValue;
	
	public abstract int search();
	
	public void spendTime(String name){
		long start = System.nanoTime();
	//	System.out.println("如果是正数表示包含这个值:"+search());
		search();
		long end = System.nanoTime();
		long time = end - start;
		System.out.println("使用"+name+"查找花费的时间为"+time);
	}
}

package test1;

public class UseLoop extends SpendTime{
//使用Loop查找数组是否包含某个值

	public UseLoop(Integer[] arr, int targetValue){
		this.arr = arr;
		this.targetValue = targetValue;
	}

public int search() {
		for(int i =0; i < arr.length; i++){
			if (arr[i]== targetValue){
		//		System.out.println(arr[i]);
				return i;
			}
		}
		return -1;
	}
}

使用Arrays.binarySearch()方法

package test1;

import java.util.Arrays;

public class UseArraysBinary extends SpendTime{
	public UseArraysBinary(Integer[] arr, int targetValue){
		this.arr = arr;
		this.targetValue = targetValue;
	}
	//使用Arrays.binarySearch查询数组中是否含有特定值
	@Override
	public int search() {
		//System.out.println("arrLength"+ arr.length);
		Arrays.sort(arr);
		return Arrays.binarySearch(arr, targetValue);
	}
}

使用List.contains()方法

package test1;

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

public class UseList extends SpendTime{

	public UseList(Integer[] arr, int targetValue){
		this.arr = arr;
		this.targetValue = targetValue;
	}
	
	@Override
	public int search() {
		List list = Arrays.asList(arr);
		if(list.contains(targetValue))
			return 1;
		return -1;
	}
}

使用Set.contains()方法

package test1;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class UseSet extends SpendTime{
	public UseSet(Integer[] arr, int targetValue){
		this.arr = arr;
		this.targetValue = targetValue;
	}
	@Override
	public int search() {
		Set set = new HashSet(Arrays.asList(arr));
	//	System.out.println(set.size());
		if(set.contains(targetValue))
			return 1;
		return -1;
	}
}