Optimizing a binary search algorithm

Question

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 n = int.Parse(Console.ReadLine());
 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 searchingfor = int.Parse(Console.ReadLine());
 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;
 }
 }
 }
 }
}

• Cody Gray: 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?
• Vasko Yanakiev: Yes, I had to do it as an exercise.
• Vasko Yanakiev: If I replaced mid=(min+max)/2 with mid=min/2 +max/2 , will the overflow bug be solved?
• paparazzo: 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
• Cody Gray: 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.

Answer 1

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: ");
 int length = int.Parse(Console.ReadLine());
 Console.Write("Enter Search Target: ");
 int target = int.Parse(Console.ReadLine());
 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
 Console.WriteLine("Target not found");
}
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;
}

• paparazzo: I think that while can fail. The common is min < max. Common to still return m for closest.
• user73941: @Paparazzi: min < max will fail if target is not in data.
• paparazzo: 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.
• user73941: @Paparazzi: OK, but have you tested the above implementation? :-)
• paparazzo: Not looking for an argument and I don't want to test. +1

Answer 2

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;