字典未知大小 - 查找單詞是否在字典中

Question

這是一個有趣的問題。

給定一個字典的接口。它的大小，分佈和內容都是未知的。按升序排序。

此外，我們有隻是一個方法

String getWord(long index) throws IndexOutOfBoundsException 

一個方法添加到API：

boolean isInDictionary(String word)

會是什麼這個問題的最好的實現。

Answer 1

讓我們假設你的假設數據結構，其單一的方法，String getWord(long index)，是基於字典實現了usual Dictionary operations：

• 除了對來收集
• 從集合去除對
• 修改現有對值的
• 查找與特定鍵相關聯的值的

但除了最後所有的方法都隱藏起來了。

如果是這樣的話，那麼你的代碼肯定是不正確的，因爲沒有理由認爲字典以任何特定的順序存儲值，因此你不能期望你的二分搜索項目使用word.compareTo() 。

另外，您沒有catch代碼索引號在字典大小和len之間，您發現兩個字的大小大於字典大小，它不一定是2的冪，所以即使你改變了線性搜索而不是二進制，你會有一個未處理的例外，而不是字典中的單詞。

Answer 2

不，字典裏面的單詞可能沒有排序。所以你必須遍歷字典並檢查每個單詞，如果它是你正在尋找的。

如果它是排序，你的解決方案可以改進。第一個循環只需要在你的單詞之後找出最正確的輸入，你正在尋找。

Answer 3

duedl0r是正確的，你不能假定字典將被排序。

沒有任何其他信息，可能隨機搜索，你可以選擇最好的算法（已估計大小後或估計期間）

只是correcteness，在你的算法的第二部分，你應該檢查例外和處理它們，因爲，你在評論所說的，你估計只是一個上限和屏幕取詞期間還有就是你會趕上一個

編輯的可能性：只是爲了給一個更好的解釋
在未排序列表中搜索具有時間複數的下界兩者均等於爲O（n）
randomized search具有複雜等於O（k），其中ķ是在搜索的迭代。所以，你可以決定ķ。但要明白，隨機搜索不能保證成功
時ñ，字典的​​大小，是非常大的，你可以設置ķ多項一些訂單低於ñ和具有高概率是非常重要的查找的單詞

Answer 4

這是我實現

boolean isWordInTheDictionary(String word){ 
    if (word == null){ 
     return false; 
    } 
    // estimate the length of the dictionary array 
    long len=2; 
    String temp= getWord(len); 

    while(true){ 
     len = len * 2; 
     try{ 
      temp = getWord(len); 
     }catch(IndexOutOfBoundsException e){ 
      // found upped bound break from loop 
      break; 
     } 
    } 

    // Do a modified binary search using the estimated length 
    long beg = 0 ; 
    long end = len; 
    String tempWrd; 
    while(true){ 
     System.out.println(String.format("beg: %s, end=%s, (beg+end)/2=%s ", beg,end,(beg+end)/2)); 
     if(end - beg <= 1){ 
      return false; 
     } 
     long idx = (beg+end)/2; 
     tempWrd = getWord(idx); 
     if(tempWrd == null){ 
      end=idx; 
      continue; 
     } 
     if (word.compareTo(tempWrd) > 0){ 
      beg = idx; 
     } 
     else if(word.compareTo(tempWrd) < 0){ 
      end= idx; 
     }else{ 
      // found the word.. 
      System.out.println(String.format("getword at index: %s, =%s", idx,getWord(idx))); 
      return true; 
     } 
    } 
} 

讓我知道如果這是正確的