1
\$\begingroup\$

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

        }
    }
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ Commented Jan 25, 2017 at 18:01
  • \$\begingroup\$ Yes, I had to do it as an exercise. \$\endgroup\$ Commented Jan 25, 2017 at 18:25
  • \$\begingroup\$ If I replaced mid=(min+max)/2 with mid=min/2 +max/2 , will the overflow bug be solved? \$\endgroup\$ Commented Jan 25, 2017 at 18:44
  • \$\begingroup\$ 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 \$\endgroup\$
    – paparazzo
    Commented Jan 25, 2017 at 18:47
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 25, 2017 at 18:49

2 Answers 2

2
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • \$\begingroup\$ I think that while can fail. The common is min < max. Common to still return m for closest. \$\endgroup\$
    – paparazzo
    Commented Jan 25, 2017 at 18:49
  • \$\begingroup\$ @Paparazzi: min < max will fail if target is not in data. \$\endgroup\$
    – user73941
    Commented Jan 25, 2017 at 18:52
  • \$\begingroup\$ 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. \$\endgroup\$
    – paparazzo
    Commented Jan 25, 2017 at 19:01
  • \$\begingroup\$ @Paparazzi: OK, but have you tested the above implementation? :-) \$\endgroup\$
    – user73941
    Commented Jan 25, 2017 at 19:02
  • \$\begingroup\$ Not looking for an argument and I don't want to test. +1 \$\endgroup\$
    – paparazzo
    Commented Jan 25, 2017 at 19:23
1
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.