-2
\$\begingroup\$

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;
}
\$\endgroup\$
3
  • \$\begingroup\$ @BCdotWEB is it matter? It is just an algorithm. \$\endgroup\$ Commented May 21, 2021 at 9:04
  • \$\begingroup\$ @BCdotWEB I changed the tag from java to C# based on the Length property. In java it would be length. \$\endgroup\$
    – Heslacher
    Commented May 21, 2021 at 9:31
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – Heslacher
    Commented May 21, 2021 at 9:32

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\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\$ Commented May 21, 2021 at 11:43
2
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.