###Terminology###
Terminology
The term that I see more commonly used for what you are doing is "binary search""binary search". I'm I‘m sure that "bisection""bisection" is a synonym but bisection can also refer to a class of algorithms for finding roots of a polynomial.
###Time complexity###
Time complexity
The actual loop iteration limit should be exactly \$\lceil log_2(n+1) \rceil\$. Your code is expectingexpects the iteration limit to be \$\lceil\sqrt n\rceil\$, but for small values of \$n\$, this limit is too low.
###Worst case###
Worst case
###Simplification###
Simplification
Actually, your code doesn'tdoesn’t need the previously mentioned loop. It also doesn'tdoesn’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.
###Sample rewrite###
Sample rewrite
// If duplicate target then it will just return the first found which
// is not necessaritynecessarily 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;
}
###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 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###
###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.
###Sample rewrite###
// 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;
}
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 actual loop iteration limit should be exactly \$\lceil log_2(n+1) \rceil\$. Your code expects the iteration limit to be \$\lceil\sqrt n\rceil\$, but for small values of \$n\$, this limit is too low.
Worst case
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.
Sample rewrite
// If duplicate target then it will just return the first found which
// is not necessarily 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;
}
###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;
}