Exploring Powerful Searching Algorithms in C#

Introduction

Searching is a fundamental operation in computer science that involves finding specific values within a data collection.

It is used in various applications, including databases, web search engines, and data analysis. In this blog, we will explore different searching algorithms in C# that can be used to find a specific value within a data collection.

Pioneers in Cloud Consulting & Migration Services

Reduced infrastructural costs
Accelerated application deployment

Get Started

Linear Search

The linear search algorithm is also known as the sequential search algorithm. A simple search algorithm checks each element in a collection until the desired value is found. Linear search can be used for sorted and unsorted collections, but it is useful for small collections.

Here’s an example of how to implement a linear search in C#:

public static int LinearSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
        {
            return i;
        }
    }
    return -1; // target not found
}

public static int LinearSearch(int[] arr, int target)

{

for (int i = 0; i < arr.Length; i++)

{

if (arr[i] == target)

{

return i;

}

return -1; // target not found

}

The above implementation has a time complexity of O(n), where n is the collection size. As the collection size grows, the time to search the collection also grows linearly.

Binary Search

Binary search is a more efficient search algorithm that divides the collection in half at each iteration. Binary search requires the collection to be sorted in ascending or descending order.

Here’s an example of how to implement binary search in C#.

public static int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;


    while (left <= right)
    {
        int mid = (left + right) / 2;


        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return -1; // target not found
}

public static int BinarySearch(int[] arr, int target)

{

int left = 0;

int right = arr.Length - 1;

while (left <= right)

{

int mid = (left + right) / 2;

if (arr[mid] == target)

{

return mid;

}

else if (arr[mid] < target)

{

left = mid + 1;

}

else

{

right = mid - 1;

}

return -1; // target not found

}

The above implementation has a time complexity of O(log n), where n is the collection size. As the collection size grows, the time taken to search the collection grows logarithmically.

Interpolation Search

Interpolation search is a variant of binary search that works best for uniformly distributed collections. It uses an interpolation formula to estimate the position of the target element.

Here’s an example of how to implement interpolation search in C#:

public static int InterpolationSearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;


    while (left <= right && target >= arr[left] && target <= arr[right])
    {
        int pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);


        if (arr[pos] == target)
        {
            return pos;
        }
        else if (arr[pos] < target)
        {
            left = pos + 1;
        }




        else
        {
            right = pos - 1;

        }
    }
    return -1; // target not found
}

public static int InterpolationSearch(int[] arr, int target)

{

int left = 0;

int right = arr.Length - 1;

while (left <= right && target >= arr[left] && target <= arr[right])

{

int pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);

if (arr[pos] == target)

{

return pos;

}

else if (arr[pos] < target)

{

left = pos + 1;

}

else

{

right = pos - 1;

}

return -1; // target not found

}

The above implementation has a time complexity of O(√n), where n is the collection size. As the collection size grows, the time to search the collection grows slowly.

Jump Search

Jump search is another variant of binary search that works by jumping ahead by a fixed number of steps instead of dividing the interval in half.

Example:

public static int JumpSearch(int[] arr, int target)
{
    int n = arr.Length;
    int step = (int)Math.Sqrt(n);
    int prev = 0;


    while (arr[Math.Min(step, n) - 1] < target)
    {
        prev = step;
        step += (int)Math.Sqrt(n);


        if (prev >= n)
        {
            return -1; // target not found
        }


    }
    while (arr[prev] < target)
    {
        prev++;


        if (prev == Math.Min(step, n))
        {
            return -1; // target not found
        }
    }


    if (arr[prev] == target)
    {
        return prev;
    }

    return -1; // target not found
}

public static int JumpSearch(int[] arr, int target)

{

int n = arr.Length;

int step = (int)Math.Sqrt(n);

int prev = 0;

while (arr[Math.Min(step, n) - 1] < target)

{

prev = step;

step += (int)Math.Sqrt(n);

if (prev >= n)

{

return -1; // target not found

}

while (arr[prev] < target)

{

prev++;

if (prev == Math.Min(step, n))

{

return -1; // target not found

}

if (arr[prev] == target)

{

return prev;

}

return -1; // target not found

}

The above implementation has a time complexity of O(√n), where n is the collection size. As the collection size grows, the time to search the collection grows slowly.

Conclusion

Searching Algorithms are essential to computer science and have many practical applications. In this blog, we explored four different searching algorithms in C#: linear search, binary search, interpolation search, and jump search. Each algorithm has advantages and disadvantages, and the best algorithm to use depends on the application’s specific requirements.

Making IT Networks Enterprise-ready – Cloud Management Services

Accelerated cloud migration
End-to-end view of the cloud environment

Get Started

About CloudThat

CloudThat is a leading provider of Cloud Training and Consulting services with a global presence in India, the USA, Asia, Europe, and Africa. Specializing in AWS, Microsoft Azure, GCP, VMware, Databricks, and more, the company serves mid-market and enterprise clients, offering comprehensive expertise in Cloud Migration, Data Platforms, DevOps, IoT, AI/ML, and more.

FAQs

1. What are searching algorithms in C#?

ANS: – Searching algorithms in C# are designed to find the presence or location of a specific element within a data collection. These algorithms operate on various data structures, such as arrays, lists, trees, or hash tables, and provide efficient methods to locate the desired element.

2. What are some common searching algorithms in C#?

ANS: – There are several common searching algorithms implemented in C#. Some examples include:

Linear Search
Binary Search
Interpolation Search
Hashing (using hash tables)
Breadth-First Search (BFS)
Depth-First Search (DFS)

Each algorithm has its characteristics, advantages, and disadvantages regarding time complexity, space complexity, and suitability for different data types.