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 == iMax仅在i == iMin时发生，因此无需检查。

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