java - 找到损坏开始的数组索引

Question

这个问题的最佳解决方案是什么？ (小于 O(n))

给定一个正整数数组，其中连续元素增加 1 (除了不增加一个的单个元素—— "corruption"), 返回损坏开始位置的索引。

示例 1:

array: [5, 6, 7, 8, 12, 13]
indices: 0 1 2 3 4 5

损坏从索引 4 开始。

示例 2:

array: [5, 2, 3, 4, 5, 6]
indices: 0 1 2 3 4 5

损坏从索引 1 开始。

附言我的解决方案是 O(n)，我也尝试将它分成两部分，但它仍然会减少一半。

提示:有人告诉我可以使用二进制搜索。

编辑:
我的解决方案是简单地迭代数组并查看差异是大于还是小于 1。

Answer 1

尝试这样的事情

public class Main {

    public static void main(String[] args) {
        int[] nums = {5, 6, 7, 8, 12, 13};
        int res = checkArray(nums, 0, nums.length - 1);
        System.out.println("res = " + res);
    }

    public static int checkArray(int[] nums, int start, int end) {
        if (end - start < 2) {
            return end;
        } else {
            int middle = (start + end) / 2;
            int a = nums[start];
            int b = nums[middle];
            if (b - a != middle - start) {
                return checkArray(nums, start, middle);
            } else {
                return checkArray(nums, middle, end);
            }
        }
    }
}

如果数组没有损坏，它利用了子数组的第一个和最后一个元素之间的差等于它的长度这一事实。