.net 二进制搜索算法使用left = left + 1而不是left = mid + 1

tpxzln5u  于 2023-06-25  发布在  .NET
关注(0)|答案(2)|浏览(132)

我需要对下面的C#代码进行一些澄清。
我在互联网上找到的大多数C#二进制搜索代码使用left = mid + 1right = mid - 1,但我设法使其代码简单地使用left = left + 1right = 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;
        }
bgtovc5b

bgtovc5b1#

当然,你的逻辑没有问题。但是你的逻辑比以前的逻辑慢。例如,数组是“0,1,2,3,4,5,6”,然后找到“4”值。
从你的逻辑来看

target value = 4
 left = 0, right = 5 => mid = 2
 left = 1, right = 5 => mid = 3
 left = 2, right = 5 => mid = 3
 left = 3, right = 5 => mid = 4 OK!

以前的逻辑

target value = 4
 left = 0, right = 5 => mid = 2
 left = 3, right = 5 => mid = 4 OK!

如您所见,前面的逻辑使用了2个步骤。

wn9m85ua

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的整数。

相关问题