二分查找是否需要隨機訪問？

Question

我認爲二進制搜索需要一個連續的順序。我不知道我是錯的還是對的。有什麼建議？

Answer 1

你需要能夠跳到隨機位置（當前部分的中間位置），所以是的，隨機訪問是必需的。 （另外，一個要求是集合是有序的）。當然，只要你的結構是一個列表/數組。如果它是一棵二叉樹，你顯然不需要隨機訪問。

Answer 2

二進制搜索是「跳進中間」。因此，需要某種對數據的定單（這樣中間定義明確）和索引訪問而不是迭代是需要的（以便能夠跳轉，否則O（log（CollectionSize））的運行時間將不可能）。

Answer 3

您可以在不進行隨機訪問的情況下執行二分搜索。例如，二叉樹支持二進制搜索，但不支持隨機訪問（至少通常使用該術語 - 對集合中任何元素的持續複雜性訪問）。

這些元素必須按某種順序排列，以便與您正在搜索的鍵進行比較，以便您可以確定如果鍵大於某個值X，那麼它也會大於所有其他元素這比X小（或者可以使用更少而不是更大）。

雖然該關係不必與數值排序相對應，但它必須能夠根據僅與一個元素進行比較來消除元素百分比（而不僅僅是單個元素）。

Answer 4

是的。二進制搜索必須能夠以隨機（非順序）方式訪問數據結構的所有元素。

Answer 5

它必須在搜索發生之前訂購，它可以按升序或降序排序，這兩種排序的區別在於您應該在上半部分還是下半部分看下一個，並確定基於密鑰您正在尋找

int binary_search(int A[], int key, int imin, int imax) 
{ 
    // test if array is empty 
    if (imax < imin): 
    // set is empty, so return value showing not found 
    return KEY_NOT_FOUND; 
    else 
    { 
     // calculate midpoint to cut set in half 
     int imid = (imin + imax)/2; 

     // three-way comparison 
     if (A[imid] > key): 
     // key is in lower subset 
     return binary_search(A, key, imin, imid-1); 
     else if (A[imid] < key): 
     // key is in upper subset 
     return binary_search(A, key, imid+1, imax); 
     else: 
     // key has been found 
     return imid; 
    } 
} 

與升序這項工作，如果你在一個從大到小的順序排列翻轉二元運算 這樣

// three-way comparison 
      if (A[imid] < key): 
      // key is in lower subset 
      return binary_search(A, key, imin, imid-1); 
      else if (A[imid] > key): 
      // key is in upper subset 
      return binary_search(A, key, imid+1, imax); 
      else: 
      // key has been found 
      return imid; 
     } 

Answer 6

是的，這確實需要隨機訪問。二分搜索的整個想法是在每次迭代中將搜索空間再分成一半，並且爲了確定新的搜索範圍，使用索引。如果每次都必須遍歷搜索空間才能達到中點，那麼您就會否定算法的重點。

Answer 7

它值得補充的是Collections.binarySearch方法不需要搜索列表是RandomAccess情況下，它的實施將接受任何List也LinkedList如下面所示：

public static <T> 
int binarySearch(List<? extends Comparable<? super T>> list, T key) { 
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) 
     return Collections.indexedBinarySearch(list, key); 
    else 
     return Collections.iteratorBinarySearch(list, key); 
} 

BINARYSEARCH_THRESHOLD等於5000（JDK 1.8） 。當然，搜索和先前排序LinkedList是相當低效的。程序員也習慣於在數組中尋找二進制搜索，而不是鏈接列表，所以Collections.binarySearch接受非RandomAccess集合的事實可能會令人驚訝。