Bisection method

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 list = new List();
    int target;
    int[] array;
    for (int i = 0; i  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;
}

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

StackExchange Code Review Q#152085, answer score: 18