仅使用通过索引获得单词的方法在未知大小的字典中查找单词

Collections.binarySearch

\'\\uffff\'

public static class ListProxy extends AbstractList<String> implements RandomAccess
{
    @Override public String get( int index )
    {
        try {
            return getWord( index );
        } catch( IndexOutOfBoundsException ex ) {
            return \"\\uffff\";
        }
    }

    @Override public int size()
    {
        return Integer.MAX_VALUE;
    }
}

public static boolean isWordInTheDictionary( String word )
{
    return Collections.binarySearch( new ListProxy(), word ) >= 0;
}

RandomAccess

public static class ListProxy extends AbstractList<String> implements RandomAccess
{
    private int size = Integer.MAX_VALUE;

    @Override public String get( int index )
    {
        try {
            if( index < size )
                return getWord( index );
        } catch( IndexOutOfBoundsException ex ) {
            size = index;
        }
        return \"\\uffff\";
    }

    @Override public int size()
    {
        return size;
    }
}

private static ListProxy listProxy = new ListProxy();

public static boolean isWordInTheDictionary( String word )
{
    return Collections.binarySearch( listProxy , word ) >= 0;
}

#!/usr/bin/perl

$t=0;
$cur=1;
$under=0;
$EOL=int(rand(1000000))+1;
$TARGET=int(rand(1000000))+1;
if ($TARGET>$EOL)
{
  $x=$EOL;
  $EOL=$TARGET;
  $TARGET=$x;
}
print \"Looking for $TARGET with EOL $EOL\\n\";

sub testWord($)
{
  my($a)=@_;
  ++$t;
 return 0 if ($a eq $TARGET);
 return -2 if ($a > $EOL);
 return 1 if ($a > $TARGET);
 return -1;
}

while ($r = testWord($cur))
{
  print \"Tested $cur, got $r\\n\";
  if ($r == 1) { $over=$cur; }
  if ($r == -1) { $under=$cur; }
  if ($r == -2) { $over = $cur; }
  if ($over)
  {
    $cur = int(($over-$under)/2)+$under;
    $cur++ if ($cur <= $under);
    $cur-- if ($cur >= $over);
  }
  else
  {
    $cur *= 2;
  }
}
print \"Found $TARGET at $r in $t tests\\n\";

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;
        }
    }
}

public WordFindingResult FindWord(string word)
    {
        var callsCount = 0;
        var lowerLimit = new WordFindingLimit(0, null);
        var upperLimit = new WordFindingLimit(int.MaxValue, null);
        var wordToFind = new Word(word);
        var wordIndex = _initialIndex;

        while (callsCount <= _maximumCallsCount)
        {
            if (CouldNotFindWord(lowerLimit, upperLimit))
                return new WordFindingResult(callsCount, -1, string.Empty, WordFindingResult.ErrorCodes.NOT_FOUND);

            var wordFound = RetrieveWordAt(wordIndex);
            callsCount++;

            if (wordToFind.Equals(wordFound))
                return new WordFindingResult(callsCount, wordIndex, wordFound.OriginalWordString);

            else if (IsIndexTooHigh(wordToFind, wordFound))
            {
                upperLimit = new WordFindingLimit(wordIndex, wordFound);
                wordIndex = IndexConsideringTooHighPreviousResult(lowerLimit, wordIndex);
            }
            else
            {
                lowerLimit = new WordFindingLimit(wordIndex, wordFound);
                wordIndex = IndexConsideringTooLowPreviousResult(lowerLimit, upperLimit, wordToFind);
            }

        }
        return new WordFindingResult(callsCount, -1, string.Empty, WordFindingResult.ErrorCodes.CALLS_LIMIT_EXCEEDED);
    }

    private int IndexConsideringTooHighPreviousResult(WordFindingLimit maxLowerLimit, int current)
    {
        return BinarySearch(maxLowerLimit.Index, current);
    }

    private int IndexConsideringTooLowPreviousResult(WordFindingLimit maxLowerLimit, WordFindingLimit minUpperLimit, Word target)
    {
        if (AreLowerAndUpperLimitsDefined(maxLowerLimit, minUpperLimit))
            return BinarySearch(maxLowerLimit.Index, minUpperLimit.Index);

        var scoreByIndexPosition = maxLowerLimit.Index / maxLowerLimit.Word.Score;
        var indexOfTargetBasedInScore = (int)(target.Score * scoreByIndexPosition);
        return indexOfTargetBasedInScore;
    }