Check if array contains

Efficient way to check if array contains given value

How to check if array contains a given value ? This is an important interview question and frequently used operation during development. Below are the 5 ways to check that. Note the time complexity in the output for all the methods, you will understand simple for-each loop method is the efficient way compared to all.

Example: Check if array contains given value

Input: inArray = {"ABC","BCD", "CDE", "FFG"};
Check whether "CDE" present in the array
Output: Yes

Arrays.stream() Example

boolean result = Arrays.stream(inArray).anyMatch("CDE"::equals);		
if(result)
   System.out.println("Yes");

List Example

List<String> list = Arrays.asList(inArray);		
if(list.contains("CDE"))
   System.out.println("Yes");

Set Example

Set<String> values = new HashSet<String>(Arrays.asList(inArray));
if(values.contains("CDE"))
   System.out.println("Yes");

Arrays.binarySearch() Example

int res = Arrays.binarySearch(inArray, "CDE");
if(res > 0)
   System.out.println("Yes");

Note: binarySearch() can only be used on sorted arrays to yield better results.

Using Simple for-each loop

boolean res = false;
for(String str: inArray)
{
   if(str.equals("CDE"))
      res = true;
}			
if(res)
   System.out.println("Yes");

Time Complexity

Below is the example code which includes all approaches and will help in measuring and analyzing the time required for this problem.

package com.sneppets.dsalgo.examples;

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

/**
 * Efficient way to check whether an array contains particular value
 * @author sneppets.com
 */
public class CheckArrayForGivenValue {
	
	public static void main (String[] args)
	{
		String[] inArray = {"ABC","BCD", "CDE", "FFG"};
		checkForGivenValue1(inArray);
		checkForGivenValue2(inArray);
		checkForGivenValue3(inArray);
		checkForGivenValue4(inArray);
		checkForGivenValue5(inArray);
	}
	
	//Using Arrays.stream()
	private static void checkForGivenValue1(String[] inArray) {
		
		long startTime = System.nanoTime();
		boolean result = Arrays.stream(inArray).anyMatch("CDE"::equals);
		
		if(result)
		{
			System.out.println("Yes");
		}
		else
		{
			System.out.println("No");
		}
		long endTime = System.nanoTime();
		long duration = endTime - startTime;
		System.out.println("Time for method 1 (Arrays.stream()): "+ duration);	
		
	}
	
	//Using List
	private static void checkForGivenValue2(String[] inArray) {
		
		long startTime = System.nanoTime();
		List<String> list = Arrays.asList(inArray);		
		if(list.contains("CDE"))
		{
			System.out.println("Yes");
		}
		else
		{
			System.out.println("No");
		}
		long endTime = System.nanoTime();
		long duration = endTime - startTime;
		System.out.println("Time for method 2 (using list): "+ duration);
	}
	
	//Using Set
	private static void checkForGivenValue3(String[] inArray) {
		
		long startTime = System.nanoTime();
		Set<String> values = new HashSet<String>(Arrays.asList(inArray));
		if(values.contains("CDE"))
		{
			System.out.println("Yes");
		}
		else
		{
			System.out.println("No");
		}
		long endTime = System.nanoTime();
		long duration = endTime - startTime;
		System.out.println("Time for method 3 (using set): "+ duration);
	}

	//Using Arrays.binarySearch()
	private static void checkForGivenValue4(String[] inArray) {
		
		long startTime = System.nanoTime();
		int res = Arrays.binarySearch(inArray, "CDE");
		
		if(res > 0)
		{
			System.out.println("Yes");
		}
		else
		{
			System.out.println("No");
		}
		long endTime = System.nanoTime();
		long duration = endTime - startTime;
		System.out.println("Time for method 4 (using Arrays.binarySearch()): "+ duration);
		
	}
	
	//Using simple for-each loop
	private static void checkForGivenValue5(String[] inArray) {
		
		long startTime = System.nanoTime();
		boolean res = false;
		for(String str: inArray)
		{
			if(str.equals("CDE"))
			{
				res = true;
			}			
		}
		if(res)
		{
			System.out.println("Yes");
		}
		else
		{
			System.out.println("No");
		}
		long endTime = System.nanoTime();
		long duration = endTime - startTime;
		System.out.println("Time for method 5 (using simple for-each loop): "+ duration);
		
	}

}

Output

Yes
Time for method 1 (Arrays.stream()): 65053274
Yes
Time for method 2 (using list): 88524
Yes
Time for method 3 (using set): 86814
Yes
Time for method 4 (using Arrays.binarySearch()): 32074
Yes
Time for method 5 (using simple for-each loop): 18389

Conclusion

Try increasing the size of array and see the time measured for each method, you will find clearly using a simple for-each loop method is more efficient than other methods.

Recommended Posts

Reference

guest
0 Comments
Inline Feedbacks
View all comments