Как отследить последний индекс в алгоритме бинарного поиска? - PullRequest
Новая
       5

Как отследить последний индекс в алгоритме бинарного поиска?

0 голосов
/ 08 января 2019

Я решаю простой алгоритм двоичного поиска, но не могу отследить последний индекс в вопросе.

Хотя я попытался включить счетчик, но напрасно, поскольку он не дает ожидаемого результата. 

  void binarySearch(int Arr[], int Size, int Search)
   {
    int Flag=0, Counter=1, First=0, Last=Size-1, Mid;
   while(First<=Last)
      {
       Mid=(First+Last)/2;
       printf("\nGuess %d (half of %d to %d) -> ", Arr[Mid], First, 
             (Last+Counter));
           if(Arr[Mid]==Search)
              {
                  printf("spot on!");
                  Flag=1;
                   break;
             }
           else if(Arr[Mid]<Search)
             {
                printf("you're too low.");
                First=Mid+1;
             }
           else
             {
                 ++Counter;
                 printf("you're too high.");
                 Last=Mid-1;
             }
      }
   if(Flag==0)
      printf("\nElement Not Found!!");
 printf("\n");
}

Ожидаемый результат: -

Скажи, что выбрано мое число 38. Что ты собираешься делать? Сделайте бинарный поиск:

Угадай 50 (половина от 0 до 100) → ты слишком высоко.

Угадай, 25 (половина от 0 до 50) → ты слишком низок.

Угадай 37 (половина от 25 до 50) → ты слишком низок.

Угадай 43 (половина от 37 до 50) → ты слишком высоко.

Угадай 40 (половина от 37 до 43) → ты слишком высоко.

Угадай 38 (половина от 37 до 40) → на месте!

Фактический результат: -

Угадай 50 (половина от 0 до 100) -> ты слишком высокий.

Угадай 25 (половина от 0 до 50) -> ты слишком низок.

Угадай 37 (половина от 25 до 50) -> ты слишком низок.

Угадай 43 (половина от 37 до 50) -> ты слишком высокий.

// Вот мое сомнение

Угадай 40 (половина от 37 до 44) -> ты слишком высокий.

Угадай 38 (половина от 37 до 42) -> на месте!

1 Ответ

0 голосов
/ 08 января 2019

Хитрость с эффективными двоичными поисками заключается в том, что вы проверяете самый первый и самый последний элемент в массиве первым.

Очевидно, что если искомое значение находится за пределами, нет необходимости выполнять бинарный поиск; и если какой-либо конец совпадет, вы его нашли.

Однако тогда это означает, что границы для двоичного поиска являются исключительными . Когда вы вычисляете индекс для следующего проверяемого элемента, если он соответствует одной из границ, вы знаете, что совпадения нет.

В псевдокоде это означает, что мы можем записать двоичный поиск, предполагая отсортированный массив со значениями в возрастающих значениях и индексацию, начинающуюся с 0, как в C, как 

Function BinarySearch(array[], length, value):

    If (length < 1):
        # Empty array.
        Return NotFound
    End If

    If (value < array[0]):
        # Value is smaller than those in the array.
        Return NotFound
    Else If (value == array[0]):
        Return Found at index 0
    End If

    If (value > array[length - 1]):
        # Value is greater than those in the array.
        Return NotFound
    Else If (value == array[length - 1]):
        Return Found at index length - 1
    End If

    Let  iMin = 0
    Let  iMax = length - 1
    Loop:

        Let  i = (iMin + iMax) / 2   # Integer division, rounds towards zero
        If (i == iMin):
            Return NotFound
        End If

        If (array[i] < value):
            iMin = i
        Else If (array[i] > value):
            iMax = i
        Else:
            Return Found at index i
        End If
    End Loop
End Function

Когда используется целочисленное деление, а iMin и iMax неотрицательны (положительные или нулевые), i = (iMin + iMax)/2 округляется до нуля, и i == iMin происходит первым, поэтому нам не нужно явно проверять i == iMax. (То есть i == iMax происходит в этом случае только тогда, когда i == iMin, так что нет необходимости проверять.)

В цикле, когда мы обновляем iMin или iMax, мы уже рассмотрели array[iMin] или array[iMax] соответственно. iMin относится к индексу, который имеет меньшее значение, чем тот, который мы ищем, а iMax к индексу, который имеет большее значение, чем тот, который мы ищем. Итак, мы по существу рассматриваем только элементы массива с индексами больше, чем iMin, но меньше, чем iMax; исключая индексы iMin и iMax.

...