Devs.site

Array class: linear and binary search in C#

The .NET framework has a wide range of collection types for storing, organizing, filtering and finding data (hash tables, queues, stacks, bags, dictionaries, and lists), which come in handy in different scenarios.

The Array class, based on the IList interface, represents a plain and simple list of all types of variables, each one having assigned an unique integer index

In this post we will look at two methods used to find a variable inside an array


The first and most obvious way of finding an element inside an array is the one in which we go one by one until we find what we want, considering this first successful comparison the result to return.

This is how we would do a linear search if we wouldn't have any other choice

    int[] myIntArray = new int[5] { 1, 2, 3, 4, 5 };

    static int FindLinear(int element)
    {
        for (int i = 0; i < myIntArray.Length; i++)
        {
            if (myIntArray[i] == element)
            {
                return i;
            }
        }
        return -1;
    }

But, of course, in C#, you have this:

    Array.IndexOf(myIntArray, 5);

The second method can be faster in most cases but can be used only in arrays that are sorted in ascending order. It is called binary search and is faster because it discards all those ranges of elements where the element surely doesn't exist. It does it like this:

    static int FindBinary(int element)
    {
        int start = 0;
        int end = myIntArray.Length - 1;
        int middle = (start + end + 1) / 2;
        int index = -1;

        do
        {
            if (element == myIntArray[middle])
            {
                index = middle;
            }
            else if (element < myIntArray[middle])
            {
                end = middle - 1;
            }
            else
            {
                start = middle + 1;
            }

            middle = (start + end + 1) / 2;
        } while ((start <= end) && (index == -1));

        return index;
    }

I am pretty sure you have done this in programming class. First, we find the element in the middle of the array. If we're lucky and that's what we are looking for, we have our result.

If the element in the middle is greater then we have to look at the first half of the array, so we slice the array in two and do the search again only in the first part (for which we recalculate the middle point).

If the element in the middle is lower then we know we have to find our index in the second half, so we find the middle element of that second half.

Just like before, the C# Array has its own method to do this:

    Array.BinarySearch(myIntArray, 5);

Code

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace ConsoleApp
    {
        class Program
        {
            static int[] myIntArray = new int[5] { 1, 3, 5, 7, 9 };

            static int FindLinear(int element)
            {
                for (int i = 0; i < myIntArray.Length; i++)
                {
                    if (myIntArray[i] == element)
                    {
                        return i;
                    }
                }

                return -1;
            }

            static int FindBinary(int element)
            {
                int start = 0;
                int end = myIntArray.Length - 1;
                int middle = (start + end + 1) / 2;
                int index = -1;

                do
                {
                    if (element == myIntArray[middle])
                    {
                        index = middle;
                    }
                    else if (element < myIntArray[middle])
                    {
                        end = middle - 1;
                    }
                    else
                    {
                        start = middle + 1;
                    }

                    middle = (start + end + 1) / 2;
                } while ((start <= end) && (index == -1));

                return index;
            }

            static void Main(string[] args)
            {
                System.Console.Write("FindLinear{0} ", FindLinear(3));
                System.Console.Write("FindBinary{0} ", FindBinary(5));
                System.Console.Write("LinearSearch {0} ", Array.LinearSearch(myIntArray, 7));
                System.Console.Write("BinarySearch {0} ", Array.BinarySearch(myIntArray, 9));
                System.Console.ReadLine();
            }
        }
    }

Requirements

Install Microsoft Visual Studio and don't forget to check the C# language


Instructions

Create a simple console application (Visual C# / Console App (.NET Framework)

0 comments

Specify your e-mail if you want to receive notifications about new comments and replies