如何跟踪二进制搜索算法中的最后一个索引？

Question

我正在解决一个简单的二进制搜索算法，但我无法跟踪问题中的最后一个索引。

虽然，我已经尝试并包含一个计数器，但没有成功，因为它没有给我预期的输出。

  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 的一半）-> 猜对了！

Answer 1

高效二进制搜索的诀窍是首先检查数组中的第一个和最后一个元素。

很明显，如果你查找的值在外面，就不需要二分查找了；如果任何一端匹配，你就找到了。

然而，这意味着二分搜索的边界是独占的。当你计算下一个要探测的元素的索引时，如果它匹配其中一个边界，你就知道没有匹配。

在伪代码中，这意味着我们可以编写二进制搜索，假设一个排序数组的值是递增的，并且索引从 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.

如何跟踪二进制搜索算法中的最后一个索引？

How to keep track of the last index in a binary search algorithm?

c

binary-search