3
\$\begingroup\$

I was looking up some coding challenges and this looked like a fun one to solve. I tested it with the following values and it seems to work for those at least:

  • [ 5, 7, 8, 9, 11, 2, 3 ]
  • [ 5, 7, 1, 4]
  • [ 5, 7, 8, 1, 5]
  • [ 5, 1, 2, 3, 5]
  • [ 5, 5, 5]
  • [ 1 ]
  • [ 1, 2 ]
  • [ 2, 1 ]

My solution was to implement a binary search to try and find the smallest value, and if both ends of the sub-list have the same value then I will increment from the lowest value to try and work out if the lowest value lies in the first or second half of the sublist. I am not 100% confident that this part of the solution is bug free, so would appreciate any feedback on that.

I am mostly looking for feedback on my logic, as the coding standard doesn't matter to me too much in this case.

public static int findMinimum(List<Integer> input) {
  return findMinRecursive(input, 0, input.size() - 1);
}

public static int findMinRecursive(List<Integer> input, int lowestIndex, int highestIndex) {
  if (lowestIndex == highestIndex) {
    return input.get(lowestIndex);
  }
  boolean lastCheck = highestIndex - lowestIndex == 1;

  int offset = (highestIndex - lowestIndex) / 2;
  if (input.get(highestIndex) > input.get(lowestIndex)) {
    if (lastCheck) {
      return input.get(lowestIndex);
    }
    return findMinRecursive(input, lowestIndex, highestIndex / 2);
  } else if (input.get(highestIndex) < input.get(lowestIndex)) {
    if (lastCheck) {
      return input.get(highestIndex);
    }
    return findMinRecursive(input, lowestIndex + offset, highestIndex);
  } else {
    // If the numbers are equal we need to find out which direction has the minimum
    for (int i = lowestIndex; i < highestIndex; i++) {
      if (input.get(i) > input.get(lowestIndex)) {
        return findMinRecursive(input, lowestIndex + offset, highestIndex);
      } else if (input.get(i) < input.get(lowestIndex)) {
        return input.get(i);
      }
    }
    return input.get(lowestIndex);
  }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Your code has a bug. Try [3,3,3,1,1,2]. \$\endgroup\$ – Misha Feb 17 '17 at 8:17
  • \$\begingroup\$ You may want to define circular list of [Comparables] by more than an algorithm to be re-constructed from source code. \$\endgroup\$ – greybeard Jul 5 '18 at 6:55
1
\$\begingroup\$

You can fix the bug, that @Misha pointed out, by changing

    if (input.get(highestIndex) > input.get(lowestIndex)) {
      if (lastCheck) {
        return input.get(lowestIndex);
      }
      return Main.findMinRecursive(input, lowestIndex, highestIndex / 2);
    }

to

    if (input.get(highestIndex) > input.get(lowestIndex)) {
      return input.get(lowestIndex);
    }

because, if the value to the right is greater than the value to the left in the subsection you are searching through, then that subsection is already perfectly sorted in ascending order.

I also think you can achieve a very tiny performance improvement if you don't use so many calls to get(). You can store the values in properties(a.k.a. variables) first, and then use those variables/properties in place of the get(), but it's probably an almost imperceptible performance boost

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.