找到一个交替排序阵列的2个相邻阵列元素的可能组合

Question

按照惯例，我搜索了谷歌和这里的答案，但没有找到任何帮助我的东西。请记住，这是不是作业，我正在为测试而努力学习，并努力完成这个问题的答案。 有一个交替排序的数组，意味着偶数索引元素被排序并且奇数索引元素也被排序（从最小到最大数目）。 例如：现在

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

，该问题要求写一个布尔方法，接收阵列和的数，X，并返回true如果该数目是2个相邻的“砖”的可能的组合和假如果不。例如：

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

我写我的方法，而且似乎与许多工作是IS一个可能的组合，但是当它应该返回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（= 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。

Answer 2

按照dasblinkenlight的建议，一个简单的二进制搜索实现可以满足这个要求。它是有效的

public class combo { 

    public static void main(String[] args){ 
     int a[] = {1,2,5,3,6,10,9}; 
     System.out.println(FindX(a, 14)); 
    } 

    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 mid = a.length/2; 
     int toSearchFrom = 0; 
     int toSearchTill = 0; 

     if(a[mid-1]+a[mid] < x){ 
      toSearchFrom = mid; 
      toSearchTill = a.length - 1;  
     } else if(a[mid-1]+a[mid] > x){ 
      toSearchFrom = 0; 
      toSearchTill = mid - 1; 
     } 

     for(int i=toSearchFrom; i < toSearchTill; i++){ 
      if(a[i] + a[i+1] == x){ 
       return true; 
      } 
     } 
     return false; 
    } 

} 

采样输入1 - 19输出=真

采样输入2 - 14输出=假

采样输入3 - 3输出=真