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);
}
}
circular list of [Comparables]
by more than an algorithm to be re-constructed from source code. \$\endgroup\$ – greybeard Jul 5 '18 at 6:55