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
- Find Least Common Element in Unsorted Array
- Programs to Find Most Common Element in an Unsorted Array
- 2 Ways to Remove Duplicates from Sorted Array – O(n) time
- Programs to Find Common Elements between Two Unsorted Arrays
- Programs to Remove Duplicate Characters from a String in O(n) Time
- Find the Largest and Smallest Number in Unsorted Array – O(n)
- Find Numbers Repeated in Array in O(N) time without using Collections
- Remove the Duplicates from Unsorted Array in O(n) Time
- Find Second Largest Element in an Unsorted Array – O(n)
- Program to reverse a string or word