Java - 二进制插入排序 StackOverFlowError

Question

我正在尝试用java编写二进制插入排序。

    public static int binarySearch(double[] a, int max, int min, double k) {
      if (max == min) 
         return (k > a[min]) ? (min + 1) : min;
      int mid = (max + min) / 2;
      if (k == a[mid])
         return mid;
      else if (k < a[mid])
         return binarySearch(a, mid - 1, min, k);
      else
         return binarySearch(a, max, mid + 1, k);
   }

   public static void binaryInsertionSort(double[] a) {
      // TODO!!!
      for(int i = 1; i < a.length; ++i) {
         int  j = i - 1;
         double tmp = a[i];
         int l = binarySearch(a, j, 0, tmp);
         while(j >= l) {
            a[j + 1] = a[j];
            --j;
         }
         a[l] = tmp;
      }
   }

但是当我用

测试它时

      a = new double[] {1., 3., 2.};
      DoubleSorting.binaryInsertionSort (a);

它返回java.lang.StackOverflowError。我在 C++ 中使用了几乎相同的代码，使用相同的输入对其进行了测试，并且工作正常。但我不知道为什么它在Java中不起作用。

Answer 1

您应该提供一个不同的示例。像 {4., 3., 2.} 这样的序列会发生 stackoverflow 错误，而 {1., 3., 2.} 似乎没有明显的问题。

与其他序列一起运行它会导致对 binarySearch 方法进行以下调用:

[4.0, 3.0, 2.0], 0, 0, 3.0
[3.0, 4.0, 2.0], 1, 0, 2.0
[3.0, 4.0, 2.0], -1, 0, 2.0

之后，它会继续重复上次调用，直到堆栈溢出。 据我理解你的想法，你不想在这里传递-1，所以你可以只改变一行:

return binarySearch(a, Math.max(0, mid - 1), min, k);

下次遇到此类问题时，我建议您使用调试器，可能还需要结合一些额外的 System.out。