1
\$\begingroup\$

I was wondering if I can make this better:

public int BinarySearchIterative(int[]inputArray, int Key) {
        int min = 0;
        Array.Sort(inputArray);
        int max = inputArray.Length;
        return BinarySearchIterative(inputArray,Key,min,max,0);
    }

    public int BinarySearchIterative(int[] inputArray, int key, int min, int max,int LoopCount) {
        while(min <= max) {
            int mid = (min + max) / 2;
            if(key == inputArray[mid]) {
                return ++mid;
            } else if(key < inputArray[mid]) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
            LoopCount++;
        }
        return LoopCount;
    }
\$\endgroup\$

2 Answers 2

9
\$\begingroup\$

This code is wrong in a great many ways.

public int BinarySearchIterative(int[]inputArray, int Key) {

The name describes how the code is implemented, not what it does. The caller doesn't care how your search is implemented. The caller cares about what the contract of the method is: what goes in, what comes out, and what the relationship between those two things is.

Non-standard spacing.

Formals should start with a lower-cased letter.

Why an array? What if we want to binary search a list? Why ints? What if we want to binary search an array of doubles? This signature is needlessly specific.

Why return int? What if the value is not found; what value will you return then? Are you returning the value, or the index? This is nowhere clear in the signature, and therefore it needs a comment.

    int min = 0;

What is the purpose of this assignment to a variable that is only read once? You could say const int min = 0; or simply pass zero. Or not pass it at all; if you always pass zero then the callee doesn't need to have it passed, does it?

    Array.Sort(inputArray);

Someone handed you an array and you sorted it for them. What if it was already in an order they liked? You just wrecked their order. That's rude. What if it was already sorted? Then you just spent time sorting an array that was already sorted.

Consider what the contract of this method should be; should it be that the array is already sorted?

    int max = inputArray.Length;

The code crashes if the input array is null. You should detect that situation early and throw an invalid argument exception.

Again giving a name to a value that you only use once. Seems unnecessary.

    return BinarySearchIterative(inputArray,Key,min,max,0);

Non-standard spacing.

Why do min and max get names but whatever that zero is does not?

public int BinarySearchIterative(int[] inputArray, int key, int min, int max,int LoopCount) {

Why is this public? It appears to be a private implementation detail of the other method.

Again with the bad signature.

And again with the nonstandard spacing choices.

    while(min <= max) {
        int mid = (min + max) / 2;

A problem that is in practice a non-problem, but still deserves to be called out. If min + max is greater than int.MaxValue, this wraps around to a negative number, which you then divide by 2.

This is a non-problem in practice because in C# an array is pretty much never observed to have more than a billion items. But to signal to the reader that you have thought this sort of thing over, you might want to use a different expression that gives the midpoint without overflowing. Can you devise such an expression?

        if(key == inputArray[mid]) {
            return ++mid;

So there you are debugging your program and stepping through the code, and you're watching the value of mid and suddenly it changes. By doing this you make the person doing the debugging -- you -- have to remember whether they're watching the original value or the new value. Don't make yourself think. Don't mutate variables unnecessarily. Either return mid; or return mid + 1;, whichever one is correct. Don't mutate a variable you're never going to read again in order to save a couple of keystrokes.

        } else if(key < inputArray[mid]) {
            max = mid - 1;

Again, mutating your formals is a bad practice that makes it hard to debug your program. Don't do it.

        } else {
            min = mid + 1;
        }
        LoopCount++;
    }
    return LoopCount;
}

What the heck is "loopcount"?

Why is it capitalized?

Why is this the return value of the method?

What connection does it have with the problem of binary searching?

Suppose the search fails after ten loops. So you return 10. Now suppose the search succeeds and finds the element 10 is the key, so you return 10. How does the caller know whether the search succeeded or not?

Why is the count passed in at all, if you're always going to pass zero? If you want to count loops then make a local variable.

For that matter, why do you pass in min, max, etc, if you could simply compute them? Why do you have two methods, one of which just calls the other, passing things that the inner method could have computed itself?

Start over.

Start with a clear statement of the problem.

  • My method takes as it argument an IList<int> and a target int. The list must be sorted and non-null. It returns null if the target is not in the list; it returns the index of the target if it is in the list.

Now that you have a statement of the problem, write the signature:

public static int? SearchSortedList(IList<int> list, int target)

Now you have everything you need right in this method already to implement binary search, so take it from here. There's no need for an auxiliary method, and there's no need for a loop count. Can you write the body of this method correctly?

\$\endgroup\$
3
  • \$\begingroup\$ I have two methods so the user dosen't have to pass min and max. \$\endgroup\$ Commented Sep 28, 2016 at 21:56
  • \$\begingroup\$ @Paparazzi I know that's why I have an array so the user can't type in an array length of 2 and have the max be 4. \$\endgroup\$ Commented Sep 29, 2016 at 11:42
  • \$\begingroup\$ @Moder This is not adding value. I was just trying to help. \$\endgroup\$
    – paparazzo
    Commented Sep 29, 2016 at 11:45
2
\$\begingroup\$

Binary search algorithm

Looks OK but a few things

check for key out of the min max

why return ++mid; ?
I think that should be return mid;

Why return LoopCount;
You don't know that means fail

I see the value of two signature. User may want to just search a range.

I see why int. You are just not looking for an exact float very often and due to imperfect precision will have to deal with that.

This is me just doing the WIKI algorithm

    public int? BinarySearch(int[] A, int T)
    {
        // Given an array A of n elements with values or records A0 ... An−1, sorted such that A0 ≤ ... ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.[6]
        // 1. Set L to 0 and R to n − 1.
        // 2. If L > R, the search terminates as unsuccessful.
        // 3. Set m(the position of the middle element) to the floor of (L + R) / 2.
        // 4. If Am < T, set L to m + 1 and go to step 2.
        // 5. If Am > T, set R to m – 1 and go to step 2.
        // 6. Now Am = T, the search is done; return m.
        Array.Sort(A);
        int M;
        int L = 0;
        int R = A.Length - 1;
        while (L <= R)
        {
            M = (L + R) / 2;
            if      (A[M] < T) L = M + 1;
            else if (A[M] > T) R = M - 1;
            else return M;
        }
        return null;
    } 
\$\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.