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;
}