How to test if an Array contains a value in Java - Linear Search

One of the common coding question from Java interviews is how to test if an Array contains a certain value or not? This is a simple question but sometimes interview pressure makes candidates nervous. Since array in Java doesn't have any inbuilt method for search, interviewer prefers to ask this question, to see how a candidate deals with such situation. If you have good knowledge of Java API then you will immediately come to know that there are alternatives available e.g. binary search of Arrays class or taking advantage of ArrayList contains method by first converting your array to ArrayList. If you come up with those solutions, Interviewer will surely ask you to write down a method to search an element in an array without using any library method. You can easily solve this question if you know linear search or binary search algorithm.

Linear search is very simple to implement, all you need to do is loop through the array and check each value if that is the one or not.

Binary search is little tricky but not too difficult either, recursive version is very natural as well. In this tutorial, though I have given two solutions, one is using ArrayList, and second is using linear search, leaving binary search an exercise for you.

But you must remember to sort array before using binary search. By the way to make the question more challenging, I usually asked the candidate to write a parametric method using generic so that it will work for any type of object array in Java.




How to check if array contains a value in Java

To give you more idea of problem, let's see an example; suppose I have a String[] with values like so:

public static final String[] names = new String[] {"Java","JEE","Scala","C++"};

Given String name, you need to return true or false, depending upon whether names contains that value or not. By the way, here is a full example of how to search a number on integer array and searching for a name on String array. This example contains two methods isExists() and contains() which returns true if the value is present in the array. The first method uses contains() method of ArrayList by first converting given an array to ArrayList, while the second method simply uses a linear search algorithm to search on a Java array. If you are using Eclipse IDE, just copy paste the code and run it, you don't need to create Java source file, Eclipse will take care of that, provided you have selected a Java project.


import java.util.Arrays;
/**
* Java Program to check if an array contains a value or not. Basically this program tells you
* how to search for an element in array, it could be an integer number or String value. 
*
* @author Javin Paul
*/
public class ArrayTest{

    public static void main(String args[]) {

        //test our method to see if array contains a certain value or not
        Integer[] input = new Integer[]{1, 2, 3, 4, 5};
        System.out.printf("Does array %s has %s?  %b %n", Arrays.toString(input), 5, isExists(input, 5));
        System.out.printf("Does array %s contains %s?  %b %n", Arrays.toString(input), 5, contains(input, 5));
        System.out.printf("Does array %s has %s?  %b %n", Arrays.toString(input), 6, isExists(input, 6));
        System.out.printf("Does Integer array %s contains %s?  %b %n", Arrays.toString(input), 6, contains(input, 6));

        String[] names = new String[]{"JP", "KP", "RP", "OP", "SP"};
        System.out.printf("Does array %s has %s?  %b %n", Arrays.toString(names), "JP", isExists(names, "JP"));
        System.out.printf("Does String array %s contains %s?  %b %n", Arrays.toString(names), "JP", contains(names, "JP"));
        System.out.printf("Does array of names %s has %s?  %b %n", Arrays.toString(names), "MP", isExists(names, "MP"));
        System.out.printf("Does array %s contains %s?  %b %n", Arrays.toString(names), "UP", contains(names, "UP"));

    }

    /**
     * Function to test if Array contains a certain value or not. This method take advantage of
     * contains() method of ArrayList class, by converting array to ArrayList.
     *
     * @return true if array contains 
     */
    public static <T> boolean isExists(final T[] array, final T object) {
        return Arrays.asList(array).contains(object);
    }


   /**
     * Another method to search an item in Java array. This method loop through array and use
     * equals() method to search element. This actually performs a linear search over array in Java
     *
     *@return true if array has provided value.
     */
    public static <T> boolean contains(final T[] array, final T v) {
        for (final T e : array) {
            if (e == v || v != null && v.equals(e)) {
                return true;
            }
        }

        return false;
    }

}

Output:
Does array [1, 2, 3, 4, 5] has 5?  true
Does array [1, 2, 3, 4, 5] contains 5?  true
Does array [1, 2, 3, 4, 5] has 6?  false
Does Integer array [1, 2, 3, 4, 5] contains 6?  false
Does array [JP, KP, RP, OP, SP] has JP?  true
Does String array [JP, KP, RP, OP, SP] contains JP?  true
Does array of names [JP, KP, RP, OP, SP] has MP?  false
Does array [JP, KP, RP, OP, SP] contains UP?  false

You can see the result as true or false if array contains a particular value or not. Like in first output array contains 5 so the result is true but in the third example, the array doesn't contain 6 so the result is false.

How to check if array contains a particular value in Java



That's all on how to find if an array contains a particular value or not. As I told you, if you are allowed to use Java API then you can either use binarySearch() method of java.util.Arrays class, or you can simply convert your array to ArrayList and then call its contains() method. If  using Java API or any third party is not allowed, then you can write your own function to search an element in an array using either binary search or linear search method. If you write binary search then be prepare with both iterative and recursive method, as the interviewer will more likely to ask both of them.

Other Java Array articles article from Java67 blog
  1. How to remove element from array without using third party library (check here)
  2. 10 points about array in Java (read here)
  3. Difference between array and ArrayList in Java (see here)
  4. How to loop over array in Java (read here)
  5. 4 ways to sort array in Java (see here)
  6. How to convert Array to String in Java (read here)
  7. How to print array in Java with examples (read here)
  8. How to compare two arrays in Java (check here)
  9. How to declare and initialize multi-dimensional array in Java (see here)
  10. How to find largest and smallest number in an array in Java (read here)
  11. How to find two maximum number on integer array in Java (check here)

4 comments:

  1. There are couple of more efficient way to solve this problem
    - sort the array and use binary search
    - use BitSet

    ReplyDelete
  2. Is it not that abrupt 'return' statement is considered harmful?

    ReplyDelete
  3. Replies
    1. Thanks Suchitra, glad you find this website useful.

      Delete