CODEWITHSUNDEEP
javaarrayssortingsearchmethods
user2738319
user2738319

Reputation: 7

Method that searches an array to find certain number of nearest values

This method due to restrictions can not use ArrayLists. The method accepts an array, the desired value to find, and then the certain number of near values. It uses integers and integer arrays only. This is what I have so far

/**
    * Return the k elements of a nearest to val.
    * The array a is not changed as a result of calling this method.
    * This method throws an IllegalArgumentException if k is negative.
    * This method returns an array of zero length if k == 0 or if
    * k > a.length.
    *
    * @param a the array to be searched
    * @param val the reference value
    * @param k the number of near elements to identify
    * @return the k elements a[i] such that ABS(a[i] - val)
    * are the k smallest evaluations
    *
    */
   public static int[] nearestK(int[] a, int val, int k) {

      int x = 0;
      int[] answer = new int[k];

      if (k < x || a.length == 0 || a == null)
      {
         throw new IllegalArgumentException();
      }

      if (k == 0 || k > a.length) 
      {
         int[] badAnswer = new int[0];
         return badAnswer;
      }

      int[] copy = Arrays.copyOf(a, a.length);

      Arrays.sort(copy);

      int nearest = copy[0];   
      for (int i = 0; (i < copy.length); i++) {

         if (Math.abs(nearest - val) > Math.abs(copy[i] - val)) {
            nearest = copy[i]; x = i; 
         }   

      }

      int index = 0;
      while (index < answer.length) {

         answer[index] = nearest;
         nearest = copy[x + (index + 1)];
         index++; 

      }
      return answer;




 }

This method works sometimes but i began to realize that it only used values after the desired element.

i.e int[1,3,5,7,10,11,12} this method, if searched for 6, with 3 nearest values, would only return 7,10,11 as an array. This clearly is not correct. I am very new to java so at this point I am wondering what are some alternatives to this or ways of correcting this method.

Upvotes: 0

Views: 1102

Answers (1)

jlordo
jlordo

Reputation: 37843

Here's a clever answer: Instead of sorting the array in natural order, sort it according to the distance to val. Then, all you need to do is pick the first k elements:

public static int[] nearestK(int[] a, int val, int k) {
    // omitted your checks for brevity
    final int value = val; // needs to be final for the comparator, you can also make the parameter final and skip this line
    Integer[] copy = new Integer[a.length]; // copy the array using autoboxing
    for (int i = 0; i < a.length; i++) {
        copy[i] = a[i];
    }
    Arrays.sort(copy, new Comparator<Integer>() { // sort it with a custom comparator
        @Override
        public int compare(Integer o1, Integer o2) {
            int distance1 = Math.abs(value - o1); 
            int distance2 = Math.abs(value - o2); 
            return Integer.compare(distance1, distance2);
        }
    });
    int[] answer = new int[k]; // pick the first k elements
    for (int i = 0; i < answer.length; i++) {
        answer[i] = copy[i];
    }
    return answer;
}

Upvotes: 1

Related Questions