Binary Search Algorithm using left = left + 1 rather than left = mid + 1

Question

Please I need some clarification on the below C# code.

Most of C# binary search code I found on the internet uses left = mid + 1 and right = mid - 1 but I managed to make it code using simply left = left + 1 and right = right - 1 which from my understanding is more obvious and clear.

Not sure what is your thoughts on my below code which works perfectly well.

 public static int MyBinarySearch_5(int[] userArray, int targetValue)
 {
            int left = 0;
            int right = userArray.Length - 1;       

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

                if(userArray[mid] == targetValue)
                {
                    return mid;
                }
                else if(userArray[mid] < targetValue)
                {
                    left = left + 1;   // left = mid + 1
                }
                else
                {
                    right = right - 1;  // right = mid - 1
                }
            }


            return 0;
        }

Answer 1

Yes, it will work, even right = right +- random will work, but will work infinitlly. Binary search means it will divide range into two distinct subranges, leaving the irrelevant one by comparation condition. In your case you are not dividing anything, just plain scan entire array.

PS

All said, you touched interesting topic, there actually exist ways to divide your data to even more efficient subranges, at the cost of additional information provided. One of this approaches is to use "distribution of your data" - if you have it, you can predict next subrange.

For example, if you know you have uniform distribution (i.e you have N items, which share almost the same distance between them), searching of X in A can be done by selecting starting position at floor(X*(max(A)-min(A))/N), it is prediction of position from which search will start. Which effectively will be not too far away from your X, making log(N) into something even faster - jack pot! The same works for any kind of distribution function.

More examples: Binary search for no uniform distribution

The main rule to predict is just: best_index = length(A) * P(x <= X) where P(x <= X) is just integral from min(A) to searched X.