알 수없는 항목 수의 이진 검색

Question

검색하는 요소의 수를 모르고 인덱스를 허용하는 API를 제공한다고 가정하고 사용자가 범위를 벗어난 경우 null을 반환합니다 (여기서는 getWordFromDictionary 메서드로 구현 됨).), 어떻게 바이너리 검색을 수행하고 클라이언트 프로그램을위한 isWordInDictionary() 메소드를 구현할 수 있습니까?

이 솔루션은 효과가 있지만 초기 색인 값이 높은 수준에서 직렬 검색을 수행했습니다. 낮은 값 범위를 통한 검색은 this answer에서 영감을 얻었습니다. 나는 또한 BinarySearch Reflector (C# decompiler)에서 엿보았지만 알려진 길이의 목록이 있으므로 여전히 간격을 메꾸기를 원한다.

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에서 시작하고 쿼리 단어 (편집 또는 null)보다 사전 적으로 더 큰 값을 얻을 때까지 쿼리 색인을 두 배로 늘립니다. 그런 다음 색인을 찾을 때까지 검색 공간을 다시 좁히거나 false를 반환 할 수 있습니다.

편집 : 이것은 점근 런타임에 추가되지 않으며 여전히 N (계열 N의 항목 수) 인 경우 O (logN)입니다.

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