Bisection method

Question

Totally agree lack of { } on if else is bad practice. That is just how I roll and I can't do it at work.

Use bisection to get to the index of a target value of a sorted array in O(sqrt(array.Length))

public static void SimpleBisectTest()
{
    Random rand = new Random();
    List<int> list = new List<int>();
    int target;
    int[] array;
    for (int i = 0; i < 10000; i++)
    {
        list.Clear();
        for (int j = 0; j < i; j++)
            list.Add(rand.Next(i * 2));
        array = list.ToArray();
        target = rand.Next(i * 2);
        //target = array.Max();
        //target = array.Min();
        int? pos = SimpleBisect(array, target);
        Debug.WriteLine("target {0}  found {1}  pos {2}",target , pos == null ? "null" : array[(int)pos].ToString(), pos == null ? "null" : pos.ToString());                
        Debug.WriteLine(string.Join(", ", array));
        if (pos != null && target != array[(int)pos])
            Debug.WriteLine("FAIL");
        Debug.WriteLine("");
    }
    Debug.WriteLine("dah done");
}
public static int? SimpleBisect(int[] array, int target)
{   //if duplicate target then it will just return the first found which is not necessarity the first match in the array
    if (array == null)
        return null;
    if (array.Length == 0)
        return null;
    Array.Sort(array);  //ideally will receive sorted array
    if (target < array[0])
        return null;
    if (target > array[array.Length-1])
        return null;
    //Debug.WriteLine("target {0}  array {1} ", target, string.Join(", ", array));
    int left = 0;
    int right = array.Length - 1;
    int middle = (left + right) / 2;
    int? middleLast = null;
    int? leftLast = null;
    int? rightLast = null;
    bool oneMoreTry = true;
    int count = 0;
    int sqrtLen = (int)Math.Ceiling(Math.Sqrt(array.Length));
    int arrayLen = array.Length;
    while (array[middle] != target)
    {
        count++;   
        if(count > sqrtLen + 2 && sqrtLen > 7)  // some how it can fail on small numbers
            Debug.WriteLine("count {0} > sqrtLen+2 {1}", count, sqrtLen + 2);
        if (array[middle] > target)
        {
            right = middle;
            if (rightLast != null)
                while (array[(int)rightLast] == array[right] && right > left)
                    right--;
            rightLast = right;
        }
        else
        {
            left = middle;
            if (leftLast != null)
                while (array[(int)leftLast] == array[left] && right > left)
                    left++;
            leftLast = left;
        }               
        middle = (left + right) / 2;
        if (middleLast != null && middle == middleLast)
        {
            if (oneMoreTry && middle < arrayLen -2)
            {   //with round down can get stuck
                middle++;
                oneMoreTry = false;
            }
            else
                return null;
        }
        middleLast = middle;
    }
    return middle;
}

Answer 1

Terminology

The term that I see more commonly used for what you are doing is "binary search". I'm sure that "bisection" is a synonym but bisection can also refer to a class of algorithms for finding roots of a polynomial.

Time complexity

The time complexity of a binary search is \$O(\log n)\$ and not \$O(\sqrt n)\$ as stated in the question. Each iteration of the main loop reduces the problem by half and so the time complexity is logarithmic. For an array of 65535 elements, for example, a binary search should take at most 16 iterations and not 256 iterations.

This is probably why you needed to add this line and comment:

   if(count > sqrtLen + 2 && sqrtLen > 7)  // some how it can fail on small numbers

The actual loop iteration limit should be exactly \$\lceil log_2(n+1) \rceil\$. Your code is expecting the iteration limit to be \$\lceil\sqrt n\rceil\$, but for small values of \$n\$, this limit is too low.

Worst case

As written, your SimpleBisect() function has a worst case time complexity of \$O(n)\$. The worst case is an array such as { 1, 2, 2, 2, 2, ... , 2 } when searching for 1. This is because you have a loop that moves the right end past duplicate values one by one:

            while (array[(int)rightLast] == array[right] && right > left)
                right--;

Simplification

Actually, your code doesn't need the previously mentioned loop. It also doesn't need leftLast, middleLast, and rightLast. The reason those variables exist is to ensure that progress is made between iterations. But if you make one small alteration to your loop, then you could guarantee progress without needing all that complication.

The alteration is that instead of setting right = middle or left = middle, you instead set right = middle - 1 or left = middle + 1. By doing that, you will never have the case where left, right, and middle remain the same from one iteration to the next.

Sample rewrite

Here is how I would rewrite your function. Note that this function assumes that the input array is already sorted:

// If duplicate target then it will just return the first found which
// is not necessarity the first match in the array
public static int? SimpleBisect(int[] array, int target)
{
    if (array == null || array.Length == 0)
        return null;

    int left  = 0;
    int right = array.Length - 1;

    while (left <= right)
    {
        int middle = left + (right - left) / 2;

        if (array[middle] > target)
        {
            right = middle - 1;
        }
        else if (array[middle] < target)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }
    return null;
}

Answer 2

Kill dead code, don't comment it. Next guy along to read your code will wonder why it is there, whether someone is in the process of fixing a bug and the code shouldn't be touched, or worse, was in the process of fixing a bug and never finished. If you need to remember this code for some reason or other, use source control.

---

Instead of:

if (pos != null && target != array[(int)pos])
    Debug.WriteLine("FAIL");

Use Debug.Assert(condition, message) instead. This is actually break the program flow as if there was a breakpoint there to catch your attention directly.

---

Avoid instantiating an instance of Random in a method (at least you didn't scope it in the loop!). Random instances should almost always be placed in class scope to reduce the chance of getting the same value for every clock tick. Random seeds itself with the current time when it is instantiated, and the value produced is completely dependent on the seed.

---

Your methods are longer than I like to see. A really good method is 2-5 lines long. A reasonable method is usually not more than 10 (I don't count braces, but it won't hurt if you do--braces cause clutter too). Try splitting these up into smaller private methods that your publicly/internally facing methods call.

---

Use more vertical whitespace (newlines); your code is hard to read because I can't see which parts are logical blocks. Optimized code doesn't need to be (and shouldn't be) hard to read--leave that for obfuscated code.

---

{   //with round down can get stuck

Don't put a comment on a brace's line unless the comment is about the brace (like // end 'foo', and we all know those comments are terrible). Put that comment on its own line above the statement being commented. Robert Martin (author of Clean Code) says that a comment should always cause the programmer to cringe in shame that we couldn't make our meaning clear using just the code, even though he does admit that they are a necessary evil in certain acceptable cases. I'm not saying this is a particularly bad place for a comment, this is just food for thought.

---

For your test method--use a unit testing framework and actually write a unit test. You basically have a test here that you have to explicitly call and examine the debug output (this test only works in debug mode!) to see if it passes. A unit test framework can be found by the Test Explorer in VS or R#'s equivalent, run by the framework, and gives a clear indication, along with potential error messages, of whether it passes.

Answer 3

It seems like you're checking a lot of edge cases. Binary search (what I think you're trying to implement) is slightly different from bisection, which uses similar intuition but is primarily used to find roots of functions. As a note to your question, binary search runs in O(log n) time, which is very different from O(sqrt n) -- often orders of magnitude. It also is much simpler than all of the nested loops you have and all of the edge case checking you include. Just looking at Wikipedia, one can write:

public static int BinarySearch(int[] array, int target) {

    int left = 0;
    int right = 0;
    while (left <= right) {
        int middle = Math.Floor(((double)left+right)/2);
        if (array[middle] < target) {
            left = middle + 1;
            continue;
        }
        if (array[middle] > target) {
             right = middle - 1;
             continue;
        }
        // If you want the first element in the array that matches
        // There exists a more efficient way similar to binary search.
        // This has worst-case O(n/2) runtime.
        while (middle > 0 && array[middle] == target) {
             middle--;
        }
        return middle; // Only happens when array[middle] == target
    }
    return -1; // Failure
}

Intuitively, binary search relies on the knowledge that the array is sorted; when you see an element greater than your target, you can set the inclusive upper bound (right) to the element before that, and likewise with the reverse scenario. If you encounter an element equal, then your job is done.

Answer 4

Although the other answers made some good stylistic observations and suggestions for improvement, many have missed a critical bug lurking in this code. Here's the offending line—see if you can spot it:

middle = (left + right) / 2;

See it? Probably not; most programmers don't, and that's why it is so common. The problem here is that the addition operation (left + right) can potentially overflow. There are many different values for left and right that could cause this to happen; it simply requires that their sum be larger than the maximum positive value representable by int, which is Int32.MaxValue, or 2³¹−1.

In C#, there are a couple of different possibilities for how overflow is dealt with. If the values are constant and the compiler can catch it at compile-time, you'll get a compile-time error, unless you are performing the operation inside an unchecked block. If it can't be detected at compile time, then you will either get an OverflowException thrown (if the code is in a checked context, which is coincidentally always the case in VB.NET) or you will get two's-complement style (modulo 2ⁿ) wraparound (if in an unchecked context, which is the default in C#).

So although you aren't dealing with any scary undefined behavior, this is still a bug. Depending on your compiler settings, you will either get an exception (which you don't handle), or you will end up with a negative intermediate value that, when divided by 2, will give the wrong value for middle, deferring the exception until such time as you try and use middle to index into the array.

Note that the final result for middle should never overflow the representable range for an int, since you're dividing by 2. That's what makes this bug so insidious and difficult to detect. The code looks like it is correct. The problem manifests only in the intermediate value obtained after doing left + right, since you aren't using an infinite-precision type. This is easy to miss.

You won't run into this bug at the top of your function, where you first declare and initialize middle. Why not? Look at the code:

int left = 0;
int right = array.Length - 1;
int middle = (left + right) / 2;

You know that left is 0, and you know that right is less than the maximum positive value representable by an int, so there is no possibility for overflow. In fact, the compiler sees this as simply middle = (array.Length - 1) / 2;.

You are not so lucky inside of the while loop, though. There, if the value you seek is in the second half of the array, you'll end up assigning middle to left, and then if the array is sufficiently large (i.e., if right is sufficiently large), then the calculation of middle will overflow as described.

Perhaps not terribly likely that you'll have an array large enough (famous last words!), but still a bug waiting to strike when you least expect it.

---

One possible solution is to rearrange the computation so that you do the division before the addition. This alleviates the possibility of an overflow, but results in the following somewhat inscrutable code:

int middle = low + ((high - low) / 2);

This works, but aside from the readability concerns (which could be addressed by a comment), it is slower than the original. Even an optimizing compiler has little choice but to transform this into a nearly-literal sequence of machine instructions.

A better solution is to do the computation with an unsigned integer value (in an unchecked context, of course). That way, you'll get the wrap-around behavior as desired, and the integer being treated as unsigned ensures that the result won't be interpreted as a negative value. The code remains essentially what you had, except with the addition of some ugly casts to force the intermediate arithmetic operations to be done on an unsigned integer, and then to cast the result back to a signed integer:

int middle = (int)(((uint)low + (uint)high) / 2);

Some people will write this with a right-shift operator, e.g.:

int middle = (int)(((uint)low + (uint)high) >> 1);

but that is unnecessary and doesn't buy you anything. In C# (unlike Java), there is no explicitly unsigned right-shift operator (i.e., one that does zero-extension as opposed to sign-extension), so the casts are still required. And once you've got the casts to force an unsigned arithmetic operation, you might as well just do a division. Let the JIT compiler optimize an unsigned division by a constant 2 into an unsigned right-shift by 1—and indeed, it will do precisely that, allowing you to write the code so that it remains readable and correct.

You probably still want a comment to ensure that an overzealous maintenance programmer doesn't remove the "superfluous" casts.

Although you could convert the numbers into a floating-point space to increase the range, this will be slower—probably significantly so in a tight loop. Since it is not necessary and the problem is trivially solved by using unsigned integers, I recommend not doing this.