Blog

How to find if Array contains a value?

  • Post last modified:March 24, 2023
  • Reading time:4 mins read

Discussing 3 options to find an element in Array in Java

Introduction

  • Finding value in the collection of value is a very common and often-used operation in software development.
  • I have seen people using all kinds of approaches to solving this problem from naive to optimized.
  • In this article, we will learn the different options to find an element in Array in Java.

Input 

  • Our input array contains primitive data of ids. and we need to search if this input array contains id->3.
int[] ids = { 1,2,13,14,15,3,10,11,12,4,5,6,7,8,9 };
int inputId = 3;

Option 1

  • One of the naive approaches is to visit all the elements in the array, one element at a time.
  • Additionally tracking the status of the target element if it exists in the array.
  • As soon we see the element we toggle the status from false to true.
  • Once the loop is finished we return the status flag.
   boolean valExist = false;
   for (int id : ids) {
      if (inputId == id) {
                valExist = true;
      }
   }
   return valExist;
  • This solution works but it’s not efficient. If you look at the if condition, you will realize that we are checking that condition for all the elements.
  • Let’s say the element we are searching for is the first element, then our loop will run for all the elements, smarter would be to break from the loop as soon as we find the element.
  • By doing that we would save on computing when the element that we are finding lies in the non-last position.
boolean valExist = false;
for (int id : ids) {
    if (inputId == id) {
                valExist = true;
                break;
     }
}
return valExist;
  • We can make our code a little shorter by using return, we can return true as soon as we see the element else we return false once the loop ends. We do not need to create and maintain the status variable.
for (int id : ids) {
      if (inputId == id) {
                return true;
       }
  }
  return false;

Option 2

  • We can use ArrayLists contains a method that basically searches for the target element in the list.
  • Since this method is provided by List, we need to convert our primitive array to a list.
  • we can use one line lambda that will convert primitive to object type and create a list from it.
   return Arrays.asList(Arrays.stream(ids).boxed().toArray())
                 .contains(inputId);
  • We can use java 8 stream API to make our code functional style and much shorter.
  • We need to understand that stream api work on streams, hence we need to convert our input array to stream.
  • Arrays.stream receives the input array and converts it to streams.
  • Once we have streams now we can use many methods, one useful method for our case is to use anyMatch that will return the element that the predicate (id == inputId).
  • This makes our code much shorter and easier to read.
return Arrays.stream(ids)
          .anyMatch(id -> id == inputId);

Option 3

The above code works and it’s easy to read, but we still need to visit each element in the stream and compare.

  • If memory is not the problem and we want to optimize the compute, one of the things that we can do is to create a set from the input array.
  • We can again use functional style code to convert from primitive array to Set.
  • Now once we have Set, we can search the element in constant time. 
Set<Integer> idsSet = Arrays.stream(ids).boxed().collect(Collectors.toSet());
return idsSet.contains(inputId);

Bonus

  • Now searching for one element is a common operation, but what is more common is to search for n elements.
  • In that case is if we don’t use Set, we end up having two loops and time complexity increases to the multiplication of the length of two collections.
  • Below is the example where we are converting one of the arrays as Set and then iterating over another array and doing a search in Set operation.
  • By doing this we increase memory, but we save on computing.
int[] targetIds = { 1, 3, 6, 88, 999, 34, 44, 55};
int[] ids = { 1,2,13,14,15,3,10,11,12,4,5,6,7,8,9 };


Set<Integer> idsSet = Arrays.stream(ids).boxed().collect(Collectors.toSet());
return Arrays.stream(targetIds)
            .boxed()
            .filter(id -> !idsSet.contains(id))
            .mapToInt(a -> a)
            .toArray();

Conclusion

  • In this article, we learned different options to find elements in the array.
  • We also discuss time and space optimization and tradeoff.

Before You Leave

  • Let me know if I can be of any help to your career, I would love to chat or jump on a call. you can connect me over Linkedin.
  • If you like this content consider supporting.
  • If you want to upskill your Java skills, you should definitely check out
    Java Programming Masterclass updated to Java 17
    [ 750,000 students already enrolled, with 4.5 stars]
Tags: , , ,

Leave a Reply