二進制搜索帶有未知數目的項目

Question

假設你不知道你正在搜索的元素的數量，並給出一個接受索引的API，並且如果你超出邊界將返回null（這裏用getWordFromDictionary方法實現），如何執行二分查找併爲客戶端程序實現isWordInDictionary（）方法？

這個解決方案的工作原理，但我最終做了一個串行搜索以上的水平，我發現了一個初始的高指數值。通過較低範圍的值搜索受到this answer的啓發。我也在BinarySearch的Reflector（C＃反編譯器）中看過，但它有一個已知的列表長度，所以仍然在填補空白。

private static string[] dictionary; 

static void Main(string[] args) 
{ 
    dictionary = System.IO.File.ReadAllLines(@"C:\tmp\dictionary.txt"); 

    Console.WriteLine(isWordInDictionary("aardvark", 0)); 
    Console.WriteLine(isWordInDictionary("bee", 0)); 
    Console.WriteLine(isWordInDictionary("zebra", 0)); 
    Console.WriteLine(isWordInDictionaryBinary("aardvark")); 
    Console.WriteLine(isWordInDictionaryBinary("bee")); 
    Console.WriteLine(isWordInDictionaryBinary("zebra")); 
    Console.ReadLine(); 
} 

static bool isWordInDictionaryBinary(string word) 
{ 
    // assume the size of the dictionary is unknown 

    // quick check for empty dictionary 
    string w = getWordFromDictionary(0); 
    if (w == null) 
     return false; 

    // assume that the length is very big. 
    int low = 0; 
    int hi = int.MaxValue; 

    while (low <= hi) 
    { 
     int mid = (low + ((hi - low) >> 1)); 
     w = getWordFromDictionary(mid); 

     // If the middle element m you select at each step is outside 
     // the array bounds (you need a way to tell this), then limit 
     // the search to those elements with indexes small than m. 
     if (w == null) 
     { 
      hi = mid; 
      continue; 
     } 

     int compare = String.Compare(w, word); 
     if (compare == 0) 
      return true; 

     if (compare < 0) 
      low = mid + 1; 
     else 
      hi = mid - 1; 
    } 

    // punting on the search above the current value of hi 
    // to the (still unknown) upper limit 
    return isWordInDictionary(word, hi); 
} 


// serial search, works good for small number of items 
static bool isWordInDictionary(string word, int startIndex) 
{ 
    // assume the size of the dictionary is unknown 
    int i = startIndex; 
    while (getWordFromDictionary(i) != null) 
    { 
     if (getWordFromDictionary(i).Equals(word, StringComparison.OrdinalIgnoreCase)) 
      return true; 
     i++; 
    } 

    return false; 
} 

private static string getWordFromDictionary(int index) 
{ 
    try 
    { 
     return dictionary[index]; 
    } 
    catch (IndexOutOfRangeException) 
    { 
     return null; 
    } 
} 

終極密碼後回答

static bool isWordInDictionaryBinary(string word) 
{ 
    // assume the size of the dictionary is unknown 

    // quick check for empty dictionary 
    string w = getWordFromDictionary(0); 
    if (w == null) 
     return false; 

    // assume that the number of elements is very big 
    int low = 0; 
    int hi = int.MaxValue; 

    while (low <= hi) 
    { 
     int mid = (low + ((hi - low) >> 1)); 
     w = getWordFromDictionary(mid); 

     // treat null the same as finding a string that comes 
     // after the string you are looking for 
     if (w == null) 
     { 
      hi = mid - 1; 
      continue; 
     } 

     int compare = String.Compare(w, word); 
     if (compare == 0) 
      return true; 

     if (compare < 0) 
      low = mid + 1; 
     else 
      hi = mid - 1; 
    } 

    return false; 
} 

Answer 1

所以，我不知道我完全從你的描述明白的問題，但我假設你正在試圖通過搜索排序未知長度的數組，以查找特定的字符串。我還假設實際數組中沒有空值;如果您要求索引超出範圍，該數組僅返回null。

如果這些事情是真的，解決方案應該只是一個標準的二進制搜索，儘管你在整個整數空間搜索，而你只是把null看作是找到一個字符串，對於。基本上可以想象，你的N個字符串的排序數組實際上是一個INT_MAX字符串的排序數組，最後用空值排序。

我不明白的是，你似乎基本上已經做到了這一點（至少從粗略的看代碼），所以我想我可能完全不瞭解你的問題。

Answer 2

當然可以。從索引1開始，並將查詢索引加倍，直到找到詞素大於查詢詞（Edit：或null）的詞。然後，您可以再次縮小搜索空間，直到找到索引，或返回false。

編輯：請注意，這不會添加到您的漸近運行時，它仍然是O（logN），其中N是系列中的項目數。

Answer 3

您可以在兩個階段實現二進制搜索。在第一階段，您將擴大搜索範圍的大小。一旦檢測到您處於界限之外，就可以在您找到的最近間隔內執行常規二分查找。像這樣：

bool isPresentPhase1(string word) 
{ 
    int l = 0, d = 1; 
    while(true) // you should eventually reach an index out of bounds 
    { 
    w = getWord(l + d); 
    if(w == null) 
     return isPresentPhase2(word, l, l + d - 1); 
    int c = String.Compare(w, word); 
    if(c == 0) 
     return true; 
    else if(c < 0) 
     isPresentPhase2(value, l, l + d - 1); 
    else 
    { 
     l = d + 1; 
     d *= 2; 
    } 
    } 
} 

bool isPresentPhase2(string word, int lo, int hi) 
{ 
    // normal binary search in the interval [lo, hi] 
}