java - 查找交替排序数组的 2 个相邻数组元素的可能组合

Question

像往常一样，我在谷歌和这里搜索了答案，但找不到任何对我有帮助的东西。请记住，这不是作业不是，我正在为考试而学习，并且正在努力完成这个问题的答案。有一个交替排序的数组，意思是，偶数索引元素被排序，奇数索引元素也被排序(从最小到最大数字)。例如:

int a[] = {1,2,5,3,6,10,9};

现在，问题要求编写一个 boolean 方法，它接收一个数组和一个数字 x，如果该数字是 2 个相邻“方 block ”的可能组合，则返回 true，否则返回 false。例如:

x = 9; 
FindX(a,9) -> true;
a[3](3) + a[4](6) = 9.

我已经编写了我的方法，它似乎可以处理一个是可能组合的数字，但是当它应该返回 false 时，当该数字在可能的 2 范围内时它会卡住组合。

  public static boolean FindX(int a[], int x){

    if (a.length==1) { // The question specifies if it's an array with 1 element is should return false. 
        return false;
    }

    int i=(a.length-1)/2; // The middle index
    int i2=i+1; // The adjacent index
    for (; i>=0 && i2<a.length;){ // beginning of loop, if either index is out of bounds, terminates look
        if (a[i]+a[i2]==x) { // once you reach the proper index (when x is within) it returns true
            return true;
        }

        else if (a[i]+a[i2]>x){ // if x is smaller than current combo, make the new index in the new bounds
            i = (i/2)+1;
            i2 = i+1;
        }

        else if (a[i]+a[i2]<x){ // same as above boolean, but opposite situation
            i = (i2+a.length)/2;
            i2 = i+1;
        }
    }
    return false;
}

每当我输入可能的组合时，它都会起作用。但是，如果我输入 14，我在 9 (=a[3](3) + a[4](6)) 和 16 (=a[ 4](6) + a[5](10)) 它会永远循环，我想不出合适的退出方式。如果数字超出可能的组合但不在范围内，它会返回 false，但对于中间数字我会卡住。答案必须在内存和时间复杂度上尽可能高效。

提前致谢。

Answer 1

您错误地实现了二进制搜索:i和 i2指向中间和“中间加一”，同时您应该保持一个索引指向有效范围的开头，一个指向有效范围的结尾。

要正确实现这一点，首先考虑一个由相邻项之和组成的假想数组:

int a[] = {1,2,5,3,6,10,9};
int s[] = { 3,7,8,9,16,19};

这个虚构的数组将有 a.length-1元素，它会按升序排序。

这个观察用一个完全排序的“方便”序列替换了两个交替排序的“不方便”序列。您可以通过使用二进制搜索来搜索此序列来找到问题的答案。

您不需要显式创建此数组。为索引编写一个经典的二进制搜索实现 0通过a.length-2 , 包括在内，但不是写 s[mid] < x写a[mid]+a[mid+1] < x .