¿Cómo verificar si una matriz contiene un valor en Java de manera eficiente?

¿Cómo comprobar si una matriz (sin clasificar) contiene un valor determinado? Esta es una operación muy útil y de uso frecuente en Java. También es una de las preguntas más votadas en Stack Overflow. Como se muestra en las respuestas más votadas, esto se puede hacer de varias maneras diferentes, pero la complejidad del tiempo podría ser muy diferente. A continuación, mostraré el costo de tiempo de cada método.

1. Cuatro formas diferentes de comprobar si una matriz contiene un valor

1) Utilizando List:

public static boolean useList(String[] arr, String targetValue) {
	return Arrays.asList(arr).contains(targetValue);
}

2) Utilizando Set:

public static boolean useSet(String[] arr, String targetValue) {
	Set<String> set = new HashSet<String>(Arrays.asList(arr));
	return set.contains(targetValue);
}

3) Usando un bucle simple:

public static boolean useLoop(String[] arr, String targetValue) {
	for(String s: arr){
		if(s.equals(targetValue))
			return true;
	}
	return false;
}

4) Utilizando Arrays.binarySearch():
binarySearch() SOLO se puede utilizar en matrices ordenadas. Si la matriz está ordenada, puede usar el siguiente código para buscar el elemento de destino:

public static boolean useArraysBinarySearch(String[] arr, String targetValue) {	
	int a =  Arrays.binarySearch(arr, targetValue);
	if(a > 0)
		return true;
	else
		return false;
}

2. Complejidad del tiempo

El costo de tiempo aproximado se puede medir usando el siguiente código. La idea básica es buscar una matriz de tamaño 5, 1k, 10k. Puede que el enfoque no sea preciso, pero la idea es clara y simple.

public static void main(String[] args) {
	String[] arr = new String[] {  "CD",  "BC", "EF", "DE", "AB"};
 
	//use list
	long startTime = System.nanoTime();
	for (int i = 0; i < 100000; i++) {
		useList(arr, "A");
	}
	long endTime = System.nanoTime();
	long duration = endTime - startTime;
	System.out.println("useList:  " + duration / 1000000);
 
	//use set
	startTime = System.nanoTime();
	for (int i = 0; i < 100000; i++) {
		useSet(arr, "A");
	}
	endTime = System.nanoTime();
	duration = endTime - startTime;
	System.out.println("useSet:  " + duration / 1000000);
 
	//use loop
	startTime = System.nanoTime();
	for (int i = 0; i < 100000; i++) {
		useLoop(arr, "A");
	}
	endTime = System.nanoTime();
	duration = endTime - startTime;
	System.out.println("useLoop:  " + duration / 1000000);
}

Resultado:

useList:  13
useSet:  72
useLoop:  5

Utilice una matriz más grande (1k):

String[] arr = new String[1000];
 
Random s = new Random();
for(int i=0; i< 1000; i++){
	arr[i] = String.valueOf(s.nextInt());
}

Resultado:

useList:  112
useSet:  2055
useLoop:  99
useArrayBinary:  12

Utilice una matriz más grande (10k):

String[] arr = new String[10000];
 
Random s = new Random();
for(int i=0; i< 10000; i++){
	arr[i] = String.valueOf(s.nextInt());
}

Resultado:

useList:  1590
useSet:  23819
useLoop:  1526
useArrayBinary:  12

Claramente, usar un método de bucle simple es más eficiente que usar cualquier colección. Muchos desarrolladores utilizan el primer método, pero es ineficaz. Enviar la matriz a otra colección requiere recorrer todos los elementos para leerlos antes de hacer algo con el tipo de colección.

La matriz debe estar ordenada, si Arrays.binarySearch() se utiliza el método. En este caso, la matriz no está ordenada, por lo tanto, no debe usarse.

En realidad, si necesita verificar si un valor está contenido en alguna matriz / colección de manera eficiente, una lista o árbol ordenado puede hacerlo en O(log(n)) o hashset puede hacerlo en O(1).