我需要对下面的C#代码进行一些澄清。
我在互联网上找到的大多数C#二进制搜索代码使用left = mid + 1和right = mid - 1,但我设法使其代码简单地使用left = left + 1和right = right - 1,从我的理解是更明显和清晰的。
不知道你对我下面的代码的想法是什么,它工作得很好。
public static int MyBinarySearch_5(int[] userArray, int targetValue)
{
int left = 0;
int right = userArray.Length - 1;
while(left <= right)
{
int mid = (left + right) / 2;
if(userArray[mid] == targetValue)
{
return mid;
}
else if(userArray[mid] < targetValue)
{
left = left + 1; // left = mid + 1
}
else
{
right = right - 1; // right = mid - 1
}
}
return 0;
}
2条答案
按热度按时间bgtovc5b1#
当然,你的逻辑没有问题。但是你的逻辑比以前的逻辑慢。例如,数组是“0,1,2,3,4,5,6”,然后找到“4”值。
从你的逻辑来看
以前的逻辑
如您所见,前面的逻辑使用了2个步骤。
wn9m85ua2#
是的,它会工作,甚至
right = right +- random
也会工作,但会无限地工作。二分搜索是指将范围划分为两个不同的子范围,保留不相关的一个,通过比较条件。在您的情况下,您不分割任何东西,只是简单扫描整个阵列。PS
总之,你触及了有趣的主题,实际上有方法将数据划分为更有效的子范围,以提供额外的信息为代价。其中一种方法是使用“数据的分布”-如果你有它,你可以预测下一个子范围。
例如,如果你知道你有均匀的分布(即你有N个项目,它们之间的距离几乎相同),在
A
中搜索X
可以通过选择floor(X*(max(A)-min(A))/N)
的起始位置来完成,这是对搜索开始位置的预测。这有效地将不会太远离你的X
,使log(N)
成为更快的东西-杰克锅!这同样适用于任何类型的分布函数。更多示例:Binary search for no uniform distribution
预测的主要规则是:
best_index = length(A) * P(x <= X)
,其中P(x <= X)
是从min(A)
到搜索的X
的整数。