# Optimizing a binary search algorithm

I have implemented a binary search algorithm in C#. Can anyone give me suggestions on improving its effectiveness?

using System;

namespace bs2
{
class Program
{
static void Main(string[] args)
{
int[] arr = new int[n];

for(int i=0;i<n;i++)
{
arr[i] = i*14; //14 is a random number, I multiply by a number so that arr[i] would not be equal to i.
}

int min = 0;int max = n-1;int mid = (n-1)/2;
while (true)
{
if (arr[mid] == searchingfor)
{
Console.WriteLine("Element is on position {0}", mid);
break;
}else if (arr[mid] < searchingfor)
{
min = mid;
mid = (min + max) / 2;
}else if (arr[mid] > searchingfor)
{
max = mid;
mid = (min + max) / 2;
}
}

}
}
}

• You are aware that both the Array and List<T> classes have a BinarySearch method, right? That one won't have the overflow bug your code does. I assume you are reinventing this wheel for strictly pedagogical purposes? Jan 25, 2017 at 18:01
• Yes, I had to do it as an exercise. Jan 25, 2017 at 18:25
• If I replaced mid=(min+max)/2 with mid=min/2 +max/2 , will the overflow bug be solved? Jan 25, 2017 at 18:44
• Try searching for a value not in the array. Why not just go with a proven (and fairly simple) algorithm? en.wikipedia.org/wiki/Binary_search_algorithm Jan 25, 2017 at 18:47
• Well yeah that would work, but it will be slower because you are now doing two divisions, which are the slowest possible arithmetic operation. Even though the JIT compiler will optimize a division by constant 2 into a bitwise shift, it's still slower than the other more optimal ways of writing the expression that I describe in the linked answer. Jan 25, 2017 at 18:49

The core of your search algorithm is OK except for one thing:

The while(true) loop will run forever, if the searchingFor is not in the array.

In addition you should organize your code properly by separating functionality: test input/output in one function and the algorithm in another:

void TestBinarySearch()
{
Console.Write("Enter Array Length: ");
Console.Write("Enter Search Target: ");

Random rand = new Random(5);
int[] data = Enumerable.Range(0, length).Select(n => rand.Next(length)).OrderBy(d => d).ToArray();
int foundIndex = BinarySearch(data, target);
if (foundIndex >= 0)
Console.WriteLine(\$"Target found at: {foundIndex}");
else
}

int BinarySearch(int[] data, int target)
{
int min = 0;
int max = data.Length - 1;
int mid = (data.Length - 1) / 2;

while (min != mid && max != mid)
{
if (data[mid] == target)
{
return mid;
}

if (data[mid] < target)
{
min = mid;
mid = (min + max) / 2;
}
else if (data[mid] > target)
{
max = mid;
mid = (min + max) / 2;
}
}

return -1;
}

• I think that while can fail. The common is min < max. Common to still return m for closest. Jan 25, 2017 at 18:49
• @Paparazzi: min < max will fail if target is not in data.
– user73941
Jan 25, 2017 at 18:52
• I just tested using this en.wikipedia.org/wiki/Binary_search_algorithm and it does not fail in target outside the range. And I hold with my statement. Jan 25, 2017 at 19:01
• @Paparazzi: OK, but have you tested the above implementation? :-)
– user73941
Jan 25, 2017 at 19:02
• Not looking for an argument and I don't want to test. +1 Jan 25, 2017 at 19:23

It fails (loops infinitely) if the number is not in the array

You fail to test on possible duplicate values

You don't need mid = (min + max) / 2; in two spots and it can overflow

You can add or subtract 1 as you know the current mid is not good

The wiki implementation is simpler and faster
I know missing if else { }

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;