非分明数数组中的幻数索引

Question

有一项任务是在一个排序数组中找到一个索引，使Ai =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进行更好的优化，但对于这样的问题来说，这并不是必要的。