Binary Search Algorithm Difference

Question

As far as I test, there is no any bug point tested. However, I wonder that if there is a problem with the usage of arr.Length or arr.Length - 1. Further, as to the boundaries like begin <= end with end = mid - 1 or begin < end with end = mid as in the codes.

// size is array length

private static int BinarySearch(int[] arr, int element)
{
    int begin = 0;
    int end = arr.Length;

    for (; begin < end ;)
    {
        int mid = begin + (( - begin + end) / 2);
        if (arr[mid] == element) return mid;
        if (arr[mid] > element)
        {
            // in left
            end = mid;
        }
        else
        {
            begin = mid + 1;
        }
    }
    return -1;
}

// size is array length - 1

private static int BinarySearch(int[] arr, int element)
{
    int begin = 0;
    int end = arr.Length - 1;

    for (; begin < end ;)
    {
        int mid = begin + (( - begin + end) / 2);
        if (arr[mid] == element) return mid;
        if (arr[mid] > element)
        {
            // in left
            end = mid;
        }
        else
        {
            begin = mid + 1;
        }
    }
    return -1;
}

@BCdotWEB I changed the tag from java to C# based on the Length property. In java it would be length. — Heslacher
– Heslacher, Commented May 21, 2021 at 9:31
@snr it matters because we review the code. We maybe comment on namings which are part of a naming-guideline which are different for different languages. — Heslacher
– Heslacher, Commented May 21, 2021 at 9:32

Heslacher · Accepted Answer · 2021-05-21 10:01:30Z

2

As far as I test, there is no any bug point tested.

Well, then you didn't test all of the edge cases, did you?

Given the array int[] arr = new[] { 1, 2, 3, 4, 5 }; I would at least test for the following edge-cases:

first item -> 0 == BinarySearch(arr, 1);
middle item -> 2 == BinarySearch(arr, 3);
last item -> 4 == BinarySearch(arr, 5);
non existing positive-item -> -1 == BinarySearch(arr, 6);
always check for zero -> -1 == BinarySearch(arr, 0);
non existing negativ-item -> -1 == BinarySearch(arr, -1);

That beeing said, the second version fails on the last-item-check.

answered May 21, 2021 at 10:01

Heslacher

51k5 gold badges83 silver badges177 bronze badges

\$\begingroup\$ Thank you sir. Any idea as to the boundaries like begin <= end with end = mid - 1 or begin < end with end = mid as in the codes? \$\endgroup\$

Soner from The Ottoman Empire
– Soner from The Ottoman Empire

2021-05-21 11:43:41 +00:00
Commented May 21, 2021 at 11:43

Add a comment |

Rick Davin · Accepted Answer · 2021-05-21 12:09:48Z

I would like to elaborate on some of the comments regarding tagging with post with the correct language. As @Heslacher states, each language has its own standards and conventions.

In C#, method naming suggests that BinarySearch is a poor name for your method. A more suitable name would be FindIndex or FindIndexUsingBinarySearch. The latter is definitely wordier but leaves little doubt as to what the method does.

The comment // in left is not needed as it tells a developer nothing that he or she doesn't already know.

A binary search requires a sorted array, or more precisely to your method, an array sorted in ascending order. With C#, the abbreviated parameter name of arr is frowned upon. Instead, it should be array or perhaps even sortedArray.

Turning to your 2 methods and the use of begin, end, and mid. In both methods, begin and mid are inclusive indices to the sorted array, but end is an exclusive index in the first version but an inclusive index in the second. Understanding this provides insights on how to correct the second version.

This original line:

int mid = begin + (( - begin + end) / 2);

For the first method should be:

int mid = begin + ((end - begin) / 2);

And for the second method, where end is inclusive, should be:

int mid = begin + ((end - begin + 1) / 2);

In the second method, you would also need to adjust:

end = mid;

with

end = mid - 1;

Stack Exchange Network

Binary Search Algorithm Difference

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Binary Search Algorithm Difference

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions