Find the minimum value in a circular list of integers

Question

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);
  }
}

Answer 1

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