找到一個交替排序陣列的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輸出=真