解决在半排序列表中查找最小数字的更好或更有效的方法

Question

所以我有一个任务，我们要写一个方法，找到列表中最小的数字，并返回它的位置。列表已排序，但可以移动。例如CCD_ 1。

我的解决方案如下：

public class Main
{

public static <E extends Comparable<E>> int findMinIndex(E[] a) {
if(a.length == 0){
return -1;
}else{
return _findMinIndex(a, 0, a.length - 1);
}
}
private static <E extends Comparable<E>> int _findMinIndex(E[] a, int first, int last){
if(last == 0){
return last;
}
int mid = first + (last - first) / 2;
if(mid == 0 || mid == last){
return mid;
}
if(a[mid].compareTo(a[last]) < 0){
if(last - first == 1){
return mid - 1;
}
return _findMinIndex(a, first, mid);
}else{
if(last - first == 1){
return mid + 1;
}
return _findMinIndex(a, mid, last);
}
}

public static void main(String[] args) {
Integer[] a = {2, 13, 17, 23, 30, 35, 41, 45, 53, 67};
System.out.println(findMinIndex(a));
}
}

他们希望我们练习泛型类，所以这就是为什么它需要一个泛型数组。

输出应为0，因为2最小。现在它通过了所有的测试用例，但我认为它可能有太多的特殊用例，有没有更有效的方法来编写它？

Answer 1

这里有一个使用二进制搜索的解决方案，该解决方案使用稍微不同的检查来键入目标。给定以ascending order排序的值数组，旋转数组内任意两点之间的任何值组都不会包含目标值if that group is also sorted in ascending order。这是因为目标值必须位于数组从descending to ascending转换的组中。通过比较旋转数组中的一个组的第一个值和最后一个值，可以很容易地确定该组是否排序。

利用这一事实，数组只需不断地细分为组，直到组的最左边索引超过最右边索引。此时，最右边的索引或high点包含目标值，并作为解决方案返回。

public static int findMinIndex(Integer[] a) {
int low = 0;
int high = a.length-1;
// check if the array is un-rotated.
if (a[low] < a[high]) {
return 0;
}
int mid = high/2;
while (low < mid) {
if (a[low].compareTo(a[mid]) > 0) {
// It's in this range
high = mid;
} else {
low = mid;
}
mid = low + (high-low)/2;
}
return high;
}

以下是我的测试方法。

• 在1 and 1000之间创建一个N排序的随机值数组
• 将CCD_ 8分配给CCD_
• 对CCD_ 10进行迭代，每次将上一个数组旋转CCD_
• 在所有情况下，都找到了最小值的索引

int N = 10_000;
Random r = new Random();
Integer[] a = r.ints(N,1, 1000).boxed().sorted().toArray(Integer[]::new);
Integer min = a[0];
for (int i = 0; i < N; i++) {
int index = findMinIndex(a);
if (a[index] != min) {
System.out.printf("Error at index %d - %d found!%n", index, a[index]);
}
Collections.rotate(Arrays.asList(a), 1);
}

注意：[7, 8, 9, 0, 1, 2, 3, 4, 5, 6]2返回由所提供的Object array支持的列表。因此Collections.rotate可以用于旋转阵列。这对基元数组无效。

Answer 2

当我阅读您的实现时，我有和您描述的相同的想法：太多的特殊情况。

如果我正确理解任务，输入按升序排序(最低索引处的最低值，最高索引处的最高值(，但可能会发生偏移。

当你说"；一种更有效的方式来写这个"；，我认为您的意思不是运行时效率，而是代码复杂性降低。

package stackoverflow;
/**
* https://stackoverflow.com/questions/71399165/
*/
public class LocateSmallestValue {
public static void main(String[] args) {
Integer[] a1 = { 7, 8, 9, 0, 1, 2, 3, 4, 5, 6 };
System.out.println("a1: " + findMinIndex(a1));
Integer[] a2 = { 2, 13, 17, 23, 30, 35, 41, 45, 53, 67 };
System.out.println("a2: " + findMinIndex(a2));
Integer[] a3 = { 2, 3, 4, 5, 6, 7, 8, 9, 0, 1 };
System.out.println("a3: " + findMinIndex(a3));
Integer[] a4 = { 67, 2, 13, 17, 23, 30, 35, 41, 45, 53 };
System.out.println("a4: " + findMinIndex(a4));
Integer[] a5 = { 2, 3, 4, 5, 6, 1 };
System.out.println("a5: " + findMinIndex(a5));
}
/**
* @param input The input is sorted but can be shifted. [7, 8, 9, 0, 1, 2, 3, 4, 5, 6] for example.
* @return index of smallest value
*/
public static <E extends Comparable<E>> int findMinIndex(E[] input) {
if (input.length == 0) {
throw new IllegalArgumentException("input array is empty");
}
// This case handles an input that is not shifted.
if (input[0].compareTo(input[input.length - 1]) <= 0) {
return 0;
}
return _findMinIndex(input, 0);
}
private static <E extends Comparable<E>> int _findMinIndex(E[] input, int currentIndex) {
int nextIndex = currentIndex + 1;
E currentValue = input[currentIndex];
E nextValue = input[nextIndex];
if (currentValue.compareTo(nextValue) > 0) {
return nextIndex;
}
return _findMinIndex(input, nextIndex);
}
}

输出：

a1: 3
a2: 0
a3: 8
a4: 1
a5: 5