If you assume the numbers must start at 0 and be increasing by 1 you can compare the middle to the index. If the middle is the same go higher, if the middle is not, go lower.
This will give you binary search time O(log2 N). The only difference is that you are comparing with the index, rather than a fixed value.
public static void main(String... args) {
int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9};
int duplicate = findDuplicate(array);
System.out.println(duplicate);
}
private static int findDuplicate(int[] array) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = array[mid];
if (midVal == mid)
low = mid + 1;
else
high = mid - 1;
}
return high;
}
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…