# Find the minimum value in a circular list of integers

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

• Your code has a bug. Try [3,3,3,1,1,2]. – Misha Feb 17 '17 at 8:17
• You may want to define circular list of [Comparables] by more than an algorithm to be re-constructed from source code. – greybeard Jul 5 '18 at 6:55

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