arrays - 具有非不同数字的数组中的魔术索引

Question

有一个任务是在具有非不同元素的排序数组中找到一个索引，使得 A[i] = i。

CTCI中给出的解决方案是:

static int magicNonDistinct(int[] array, int start, int end) {
  if (end < start) return -1;
  int mid = start + (end - start) / 2;
  if (mid < 0 || mid >= array.length) return -1;

  int v = array[mid];
  if (v == mid) return mid;

  int leftEnd = Math.min(v, mid - 1);
  int leftRes = magicNonDistinct(array, start, leftEnd);
  if (leftRes != -1) return leftRes;

  int rightStart = Math.max(v, mid + 1);
  int rightRes = magicNonDistinct(array, rightStart, end);
  return rightRes;
}

你能指出这些索引的基本原理吗:

  int leftEnd = Math.min(v, mid - 1);
  int rightStart = Math.max(v, mid + 1);

在我的实现中，与上面的类似，这些指标计算如下:

  int leftEnd = (mid < v) ? mid - 1 : v;
  int rightStart = (mid < v) ? v : mid + 1;

谢谢。

Answer 1

这些陈述是等价的。选择您的实现还是来自 CTCI 的实现只是一个偏好问题。它们执行相同的基本操作(即返回最大值/最小值)，并且两者的效率都不比另一个高或低。我个人会选择 CTCI 实现，只是因为 Math.max 或 Math.min 很有可能被 JVM 优化得更好，但这对于像这样的问题来说不是必需的。