數組中具有非奇數的魔術索引

Question

有一項任務是找到一個索引，使得A [i] = i在具有非不同元素的有序數組中。

中鼎給出的解決方案是：

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的問題。他們正在執行相同的基本操作（I.E返回最大值/最小值），並且任何一個都不會比另一個更有效。我個人會使用CTCI實現，因爲很有可能Math.max或Math.min被JVM更好地優化，但這對於這樣的問題並不是必需的。