c - 如何跟踪二分搜索算法中的最后一个索引？

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 == iMin 时才会出现 i == iMax，因此无需检查。)

在循环中，当我们更新iMin或iMax时，我们已经检查了array[iMin]或array[iMax ] 分别。 iMin 指的是比我们要查找的值更小的索引，iMax 指的是比我们要查找的值更大的索引。因此，我们本质上只考虑索引大于iMin但小于iMax的数组元素；不包括索引 iMin 和 iMax。