面試算法：在未知長度的排序數組中進行快速查找

假設A是一個排好序的數組，但是它的長度，我們無法得知。如果我們訪問的元素超出了數組長度，那麼就會引發一次異常，請設計一個有效算法，輸入數組A以及一個數值k，找到一個下標i，使得A[i] = k, 返回-1，如果數組A中不存在等於k的元素。

這道題跟我們以前處理的查找問題不同之處在於，數組A的長度無法確定。如果數組A長度確定的話，那麼問題就退化為一個在排序數組中進行查找的問題，此時我們依靠二分查找法就能快速定位數組A是否包含給定元素。

問題在於，數組A長度無法提前確定，那麼我們就不能直接使用二分查找，因為我們無法定位中點，在使用二分查找時，我們需要知道起點b,終點e,然後定位中點m = (b+e)/2, 然後看A[m]與要查找數值的關係，如果A[m]大於k，那麼我們就可以在[b,e]中二分查找，如果A[m]小於k,那麼我們就可以在[b,e]中二分查找。由此當e不能確定時，我們無法計算m。

在不確定長度的排序數組中進行查找時，我們可以這麼做。我們依次查找A[0],A[1],A[2],A[4],…，如果A[i]比k小，那麼我們就將當前訪問元素的下標增加一倍，假定A[p]比k小，但是訪問A[2p]時越界產生了異常，那麼我們就在區間[p, 2p]間進行二分查找，當然如果在產生異常前，我們找到p,使得A[p]大於k，那麼我們就可以直接在區間[0, p]間進行二分查找就可以了。我們看看相關的實現代碼：

public class SearchingUnkownLengthSortedArray {  private int[] array = null;  public SearchingUnkownLengthSortedArray(int[] A) {  this.array = A;  }  private int binarySearch(int[] A, int k, int begin, int end) {  /*  * 在區間[begin, end]中進行二分查找，如果找到則返回下標，找不到則返回-1  */  while (begin <= end) {  int m = (begin + end) / 2;  //如果訪問A[m]出現異常，那麼把end設置為m-1，然後繼續執行二分查找  try {  if (A[m] == k) {  return m;  }  if (A[m] < k) {  begin = m + 1;  }  if (A[m] > k) {  end = m - 1;  }  }catch (ArrayIndexOutOfBoundsException e) {  System.out.println("mid point out of length: " + m);  end = m - 1;  }  }  return -1;  }  public int searchingWithUnknownLength(int k) {  /*  * 下標從0，1，2依次倍增，如果下標增加到2p時，訪問越界，那麼在[p, 2p]間進行二分查找  */  if (this.array[0] == k) {  return 0;  }  if (this.array[0] > k) {  return -1;  }  int endKeeper = 1;  while (true) {  try {  if (this.array[endKeeper] < k) {  endKeeper = endKeeper << 1;  } else if (this.array[endKeeper] == k){  return endKeeper;  }else {  return this.binarySearch(this.array, k, 0, endKeeper);  }  }catch(ArrayIndexOutOfBoundsException e) {  System.out.println("index out of array length: " + endKeeper);  return this.binarySearch(this.array, k, endKeeper >> 1, endKeeper);  }  }  } } 

注意到代碼實現中，有兩處對數組下標訪問溢出進行了捕捉。一是倍增下標，探測數組結尾時會產生數組訪問溢出，二是在binarySearch中進行二分查找時，由於給定的末尾很可能遠遠超出數組末尾，因此獲取中點m時任然有可能產生數組訪問溢出，在二分查找時，一旦出現溢出，我們可以確定數組末尾一定在當前計算的中點之前，因此調整二分查找的區間末尾後，再次進行查找即可，注意代碼實現中，從沒有考慮數組長度。

我們構造一個排序數組，然後調用上面代碼查詢給定元素，相關代碼如下：

public class Searching {  public static void main(String[] args) {  int A[] = {1, 2, 3, 4 , 5, 6, 7, 8, 9 , 10};  SearchingUnkownLengthSortedArray su = new SearchingUnkownLengthSortedArray(A);  int idx = su.searchingWithUnknownLength(10);  if (idx != -1) {  System.out.println("The given key is at index of " + idx);  } else {  System.out.println("The array do not contain the given key");  }  } }

上面代碼運行後如圖：

上面代碼運行的時間複雜度是lg(n)，其中n是數組的長度。

閱讀更多 wycl16514 的文章

關鍵字: 長度 return array