Binary Search of Array in C#

Question

I am an algo-newbie and this is my first attempt at writing binary search and it worked on the first try. But something about it tells me that its far from perfect. Please tell me how I can improve.

using System;

class Program
{
    public static void Main()
    {
        int[] arr = { 40, 67, 34, 25, 65, 87, 23 };

     
        //insertion sort 
        for (int i = 0; i < arr.Length; i++)
        {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j = j - 1;
                arr[j + 1] = key;
            }
        }
        //printing 
        Console.WriteLine("Sorted Array");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }

        void BinarySearch(int[] arr, int lowerIndex, int upperIndex, int v)
        {
            if (lowerIndex <= upperIndex)
            {
                int middleIndex = (lowerIndex + upperIndex) / 2;
                if (v == arr[middleIndex])
                {
                    Console.WriteLine("Found at " + middleIndex);
                }
                else if (v < arr[middleIndex])
                {
                    BinarySearch(arr, lowerIndex, middleIndex - 1, v);
                }
                else if (v > arr[middleIndex])
                {
                    BinarySearch(arr, middleIndex + 1, upperIndex, v);
                }
                else Console.WriteLine("Not found");
            }
        }

        //Searching for 87
        BinarySearch(arr, 0, arr.Length - 1, 87);
    }
}

Welcome to Code Review@SE. Please include some test cases, including searching for a key not present. — greybeard
– greybeard, Commented Jan 10, 2022 at 13:28
@Vogel612 yes I am using .NET 6.0.101 and that comes with C#10 — Aniruddha
– Aniruddha, Commented Jan 10, 2022 at 14:03
BinarySearch(arr, 0, arr.length - 1, 42); does not give the effect I take to be intended. — greybeard
– greybeard, Commented Jan 10, 2022 at 16:07
Validate the call arguments. null or empty array, indexes out of range, lower/upper indexes out of order — radarbob
– radarbob, Commented Jan 13, 2022 at 2:42

Enrique Castaneda · Accepted Answer · 2022-01-13 08:16:11Z

Your code tackles 2 problems, which is suboptimal when learning/asking for review:

sort an array
perform binary search

Since you are interested in binary search, you can always assume, that your input array is sorted and take it from there.

Your code for binary search looks alright apart for a little bug if an element isn't on the array. You should move your last else to the outer if:

void BinarySearchRec(int[] arr, int lowerIndex, int upperIndex, int v)
{
    if (lowerIndex <= upperIndex)
    {
        int middleIndex = (lowerIndex + upperIndex) / 2;
        if (v == arr[middleIndex])
        {
            Console.WriteLine("Found at " + middleIndex);
        }
        else if (v < arr[middleIndex])
        {
            BinarySearchRec(arr, lowerIndex, middleIndex - 1, v);
        }
        else if (v > arr[middleIndex])
        {
            BinarySearchRec(arr, middleIndex + 1, upperIndex, v);
        }  
    }
    else
    {
        Console.WriteLine("Not found");
    } 
    
}

There are however a couple of points where you might improve your code: If you are using recursion, you might want to create a public method that exposes the minimal amount of parameters and the recursive method with your full parameter list private:

public void BinarySearch(int[] arr, int v)
{
    BinarySearchRec(arr, 0, arr.Length - 1, v);
}
private void BinarySearchRec(int[] arr, int lowerIndex, int upperIndex, int v)
{
    //TODO: Implement
}

Also you are returning nothing and writing to console your result. You might want to return the index of the item whenever it is present or -1 otherwise. This way you can use your method wherever you want; also this way your method does just one thing, search for an element in an array, instead of two: search and protocol the result.

Lastly you might want to avoid recursion, since it creates an unnecessary overhead, and specially since the iterative code for this problem is almost the same:

int BinarySearch<T>(T[] arr, T val) where T : IComparable
{
    var lowerIndex = 0;
    var upperIndex = arr.Length - 1;

    while(lowerIndex <= upperIndex)
    {
        var middleIndex = lowerIndex + (upperIndex - lowerIndex) / 2;
        var compareResult = arr[middleIndex].CompareTo(val);

        if(compareResult == 0)
        {
            return middleIndex;            
        }

        if(compareResult > 0)
        {
            upperIndex = middleIndex - 1;
        }
        else
        {
            lowerIndex = middleIndex + 1;
        }
        
    }

    return -1;
}

Notice the use of IComparable Generic Types.

Now if you want to test this method, you should always test the edge cases (first element, last element, element not found) aside from any random element. This way you are sure, that your code works in both directions and yields a correct result if the element is not present:

int[] arr = { 23, 25, 34, 40, 65, 67, 87};

Console.WriteLine(BinarySearch(arr, 40)); //3
Console.WriteLine(BinarySearch(arr, 25)); //1
Console.WriteLine(BinarySearch(arr, 87)); //6
Console.WriteLine(BinarySearch(arr, 23)); //0
Console.WriteLine(BinarySearch(arr, 42)); //-1

As a last step you should use the previous Console.WriteLines and make actual test cases for your function. If anything to get used to test your code.

BinarySearchRec(arr, v); ... Are index parameters optional in BinarySearchRec? — radarbob
– radarbob, Commented Jan 13, 2022 at 2:37
@radarbob added the call with the parameters. Could have make them optional, but was beyond the scope. Thanks for letting me know. — Enrique Castaneda
– Enrique Castaneda, Commented Jan 13, 2022 at 8:17

Suryasis Paul · Accepted Answer · 2022-01-18 04:59:03Z

Taking a cue from the previous review:

var middleIndex = lowerIndex + (upperIndex - lowerIndex) / 2;

is important so that one avoids overflows.

In, the generic version of the code provided, Incorporating exception handling, what if the array is null?

if(arr == null) { throw new ArgumentNullException(); }
Also, what if the IComparable interface is not implemented by the class. Like you are getting some external code(read only), which you cannot modify. It makes sense to put an overload like:

BinarySearch(Array, Object, IComparer)
I would however disagree that:

public void BinarySearch(int[] arr, int v) should be the only available interface for the user. What if you want to search only a part of the array? So it makes sense to expose the entire:

private void BinarySearchRec(int[] arr, int lowerIndex, int upperIndex, int v) { //TODO: Implement }
In the above one must also deal with cases where the lowerIndex is greater than the upperIndex and raise an exception:
```
 if (lowerIndex > upperIndex)
```
{ throw ArgumentOutOfRangeException(); }

Stack Exchange Network

Binary Search of Array in C#

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Binary Search of Array in C#

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions