Binary Search Algorithm 使用 left = left + 1 而不是 left = mid + 1。

huangapple go评论75阅读模式
英文:

Binary Search Algorithm using left = left + 1 rather than left = mid + 1

问题

The provided C# code appears to be a binary search implementation. The key difference you've mentioned is using "left = left + 1" and "right = right - 1" instead of the more common "left = mid + 1" and "right = mid - 1" for updating the search boundaries. Your code should work correctly as well.

英文:

Please I need some clarification on the below C# code.

Most of C# binary search code I found on the internet uses left = mid + 1 and right = mid - 1 but I managed to make it code using simply left = left + 1 and right = right - 1 which from my understanding is more obvious and clear.

Not sure what is your thoughts on my below code which works perfectly well.

 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;
        }

答案1

得分: 2

当然,你的逻辑没有问题。
但是你的逻辑比以前的逻辑慢。
例如,数组是 "0, 1, 2, 3, 4, 5, 6",你要找到值为 "4" 的元素。

根据你的逻辑:

 目标值 = 4
 左边界 = 0,右边界 = 5 => 中间值 = 2
 左边界 = 1,右边界 = 5 => 中间值 = 3
 左边界 = 2,右边界 = 5 => 中间值 = 3
 左边界 = 3,右边界 = 5 => 中间值 = 4,OK!

以前的逻辑:

 目标值 = 4
 左边界 = 0,右边界 = 5 => 中间值 = 2
 左边界 = 3,右边界 = 5 => 中间值 = 4,OK!

正如你所看到的,以前的逻辑只需要2个步骤。

英文:

Of course, your logic is no problem.
But your logic is slower than previous logic.
For example, the array is " 0, 1, 2, 3, 4, 5, 6" and you find the "4" value.

From your logic

 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!

Previous logic

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

As you can see, previous logic is used 2 steps.

答案2

得分: 2

是的,它会工作,甚至 right = right +- random 也会工作,但会无限地工作。
二分查找意味着它将范围分为两个不同的子范围,通过比较条件留下相关的范围。在你的情况下,你没有分割任何东西,只是简单地扫描整个数组。

附言

总之,你触及了一个有趣的话题,实际上存在将数据分割成更高效子范围的方法,但需要提供额外的信息作为代价。其中一种方法是使用“数据的分布” - 如果你有这个信息,你可以预测下一个子范围。

例如,如果你知道你有均匀分布(即你有 N 个项目,它们之间的距离几乎相同),在 A 中搜索 X 可以通过选择起始位置 floor(X*(max(A)-min(A))/N) 来完成,这是搜索将开始的位置的预测。这实际上不会离你的 X 太远,使 log(N) 变得更快 - 大发利市!对于任何类型的分布函数都适用相同的原理。

更多示例:https://stackoverflow.com/questions/16872675/binary-search-for-no-uniform-distribution

预测的主要规则只是:best_index = length(A) * P(x <= X),其中 P(x <= X) 只是从 min(A) 到搜索的 X 的积分。

英文:

Yes, it will work, even right = right +- random will work, but will work infinitlly.
Binary search means it will divide range into two distinct subranges, leaving the irrelevant one by comparation condition. In your case you are not dividing anything, just plain scan entire array.

PS

All said, you touched interesting topic, there actually exist ways to divide your data to even more efficient subranges, at the cost of additional information provided. One of this approaches is to use "distribution of your data" - if you have it, you can predict next subrange.

For example, if you know you have uniform distribution (i.e you have N items, which share almost the same distance between them), searching of X in A can be done by selecting starting position at floor(X*(max(A)-min(A))/N), it is prediction of position from which search will start. Which effectively will be not too far away from your X, making log(N) into something even faster - jack pot! The same works for any kind of distribution function.

More examples: https://stackoverflow.com/questions/16872675/binary-search-for-no-uniform-distribution

The main rule to predict is just: best_index = length(A) * P(x <= X)
where P(x <= X) is just integral from min(A) to searched X.

huangapple
  • 本文由 发表于 2023年6月9日 11:51:51
  • 转载请务必保留本文链接:https://go.coder-hub.com/76437101.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定