Home > Back-end >  Finding multiple occcurances of the same value within a linear search on an array
Finding multiple occcurances of the same value within a linear search on an array

Time:09-17

How can I make it so if the value appears more than once in an array the code can then say the value appears in index: 0, 1, etc?

I'm working on a homework assignment that asks to write a method called linearSearch that performs a linear search on an integer array: searches starting at index 0, then 1, 2, 3…. It should return the index of the array that contains the target or a -1 if it is not found in the array. I have done that, but an issue that I am seeing is if the target appears more than once in the array the print statement will only print where it's located first. For Example, if my array is [6, 3, 9, 2, 7, 6]. The print statement says "6 is found at index: 0". Is there a way to change it when the value appears more than once so the print statement will then say "6 is found at index: 0 and 5"?

import java.util.Arrays;
import java.util.Random;

public class Q6 {
    public static void main(String[] args) {
        Random random = new Random();
        int x = random.nextInt(10);
        int[] y = createRandomIntArray(x);
        int z = x;
        System.out.println(Arrays.toString(y));
        System.out.println(z   " is found at index: "   linearSearch(y, z));
    }

    public static int[] createRandomIntArray(int n) {
        Random random = new Random();
        int[] result = new int[n];

        for (int i = 0; i < result.length; i  )
            result[i] = random.nextInt(10);
        return result;
    }

    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i  ) {
            if (array[i] == target) {
                return i;
            }
        }
        return -1;
    }

}
Output:
[6, 3, 9, 2, 7, 6]
6 is found at index: 0

CodePudding user response:

I would use a list to store each index where the target number is found, then add them all together into one string before returning them:

public static String linearSearch(int[] array, int target) {
    List<Integer> indices = new ArrayList<Integer>();
    for (int i = 0; i < array.length; i  ) {
        if (array[i] == target) {
            indices.add(i);
        }
    }

    return indices.stream().map(String::valueOf).collect(Collectors.joining(" and "));
}

But I imagine that your professor does not want you using lists yet, let alone streams. So, here is another method which creates a new array to store the indices in, making it the same size as the source array, and uses a variable matches to keep track of how many indices are stored in that array:

public static String linearSearch(int[] array, int target) {
    int[] indices = new int[array.length];

    int matches = 0;
    for (int i = 0; i < array.length; i  ) {
        if (array[i] == target) {
            indices[matches  ] = i;
        }
    }

    if (matches == 1) {
        return String.valueOf(indices[0]);
    } else {
        String builder = String.valueOf(indices[0]);

        for (int i = 1; i < matches; i  ) {
            builder  = " and "   indices[i];
        }

        return builder;
    }
}

CodePudding user response:

Rather than modify the return value of your linearSearch method to handle multiple matches you could instead add a start position for the search.

public static int linearSearch(int[] array, int target, int off) {
  for (int i = off; i < array.length; i  ) {
      if (array[i] == target) {
          return i;
      }
  }
  return -1;
}

You would then make (potentially) multiple calls, using the position of the previously identified match as the starting point of the next search. You quit when you fail to find a match.

public static void main(String[] args)
{
    int x = 6;
    int[] y = {6, 3, 9, 2, 7, 6};
    
    int off = 0;
    while(true)
    {
        off = linearSearch(y, x, off);
        if(off < 0) break;
        System.out.println("Found at index: "   off);
        off  = 1;
    }
}

Output:

Found at index: 0
Found at index: 5
  • Related