Бинарный поиск с неизвестным количеством предметов - PullRequest
Новая
       15

Бинарный поиск с неизвестным количеством предметов

1 голос
/ 08 апреля 2011

Если вы не знаете, сколько элементов вы ищете, и у вас есть API, который принимает индекс и возвращает ноль, если вы находитесь за пределами (как реализовано здесь с помощью метода getWordFromDictionary), как вы можете выполнить двоичный файл?искать и реализовывать метод isWordInDictionary () для клиентских программ?

Это решение работает, но в итоге я выполнил последовательный поиск выше уровня, где я нашел начальное значение высокого индекса.Поиск по нижнему диапазону значений был вдохновлен этим ответом .Я также заглянул в 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;
}

Ответы [ 3 ]

4 голосов
/ 08 апреля 2011

Вы можете реализовать бинарный поиск в два этапа. На первом этапе вы увеличиваете размер интервала, в котором вы ищете. Как только вы обнаружите, что выходите за границы, вы можете выполнить обычный двоичный поиск в последнем найденном интервале. Примерно так: 

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]
}
2 голосов
/ 08 апреля 2011

Конечно, вы можете. Начните с первого индекса и удваивайте индекс запроса, пока не найдете лексографически большее, чем слово запроса (Edit: или null). Затем вы можете снова сузить область поиска до тех пор, пока не найдете индекс, или вернуть false.

Редактировать: обратите внимание, что это НЕ добавляет к вашей асимптотической среде выполнения, и это все еще O (logN), где N - количество элементов в серии.

0 голосов
/ 08 апреля 2011

Итак, я не уверен, что полностью понимаю проблему из вашего описания, но я предполагаю, что вы пытаетесь найти в отсортированном массиве неизвестной длины, чтобы найти конкретную строку. Я также предполагаю, что в реальном массиве нет нулей; массив возвращает ноль только в том случае, если вы запрашиваете индекс, выходящий за границы.

Если эти вещи верны, решение должно быть просто стандартным двоичным поиском, хотя тот, в котором вы выполняете поиск по всему целочисленному пространству, и вы просто трактуете null так же, как и поиск строки, которая следует за искомой строкой. , По сути, просто представьте, что ваш отсортированный массив из N строк - это действительно отсортированный массив строк INT_MAX, отсортированных с нулями в конце.

Что я не совсем понимаю, так это то, что вы, кажется, в основном уже сделали это (по крайней мере, из беглого взгляда на код), поэтому я думаю, что, возможно, я не совсем понимаю вашу проблему.

...