class FindCorruptionIndex
{
    public static void main(String[] args) 
    {
        int i,j;
        int array[]={1,2,3,4,7,8,9};
        System.out.print("The array is [ ");
        for (int x :array )
        {
            System.out.print(x+",");
        }
        System.out.print("\b ] ");
        System.out.println();
        for(i=0;i<array.length-1;i++)
        {
            j=array[i+1]-array[i];
            if (j>=2)
            {
                System.out.println("The corruption Index position is "+(i+1));  
            }
        }   
    }
}

o（n）是你唯一的选择。二进制搜索是o（log（n）），但它只适用于在排序列表中搜索特定的数字。您既没有已排序的列表，也没有要搜索的特定数字

试试这个

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);
            }
        }
    }
}

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

public static void main(String[] args) {
    // corruption starts at 13
    int[] arr = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17};

    int corruptionIndex = -1;

    int start = 0;
    int end = arr.length;

    while (end - start > 1) {
        int middle = (start + end) / 2;

        // we add the first element onto our value as an offset
        int expectedValue = middle + arr[0];

        if (arr[middle] != expectedValue) {
            // something has already gone wrong, let's check the first half
            end = middle;
        }
        else {
            // so far so good, let's check the second half
            start = middle;
        }

        corruptionIndex = end;
    }

    System.out.println("Corruption Index: " + corruptionIndex);
}

var arr1 = [5, 9, 7, 8, 9, 13] ;
var arr2 = [5, 2] ;
var arr3 = [5, 6, 7, 8, 9, 13] ;
check(arr1);
check(arr2);
check(arr3);

function check(arr){
 for(var i=1;i<arr.length;i++){
  if(arr[i]-arr[i-1] !=1 ){
   console.log('corroption begins at '+i);
   break;
  }
 }
}

我们可以检查当前和上一个元素的差异，对吗。如果diff不是1，我们需要中断。它在js中