Linear Search and Binary Search in C#

In this post, you will learn Linear Search and Binary Search in C#. Searching algorithms have applications in many computer science applications. Basically, searching algorithms allow the user to find a target element given the list of elements. In fact, we can use two common searching techniques – The Linear Search and Binary Search to find the search target.

Linear Search

Basically, the Linear search is a technique which allows user to search a particular value from a list of values/ The list of values is available in an array. The searching starts from the beginning of the array. The linear search compares the target value with each value in the array one-by-one and stops when either the target element is found or the search reaches the end of the array.

Binary Search

Binary search makes the searching process more efficient. Just like the linear search, the objective of the binary search is also to find the target value from a list of values such as an array. In fact, the binary search doesn’t compare the target value with each element of the array. Instead, the binary search works in the following way.

We compare the target value with the middle element of the array. The binary search returns the index of the target if there is a match. Otherwise, if the target element is less than the middle element, the second half of the array is discarded and the value is again compared with the middle element of the first half of the array. In contrast, if the target value is larger than the middle element, the first half of the array is discarded and the value is compared with the middle element. The binary search repeats this process until either it finds the target element or there is no remaining element in the array.

Implementation of Searching Techniques in C#

Now we implement both searching techniques in C#. Here, we use the array with initial values for searching the target element. The user will provide the value of the target element.

Implementing Linear Search

In the following code, the function LinearSearch() performs the searching and returns the position of the target element if it is present and otherwise returns a value of -1. In fact, the loop within this function compares each element with the target until the target is found or the entire array is scanned.

using System;
namespace SearchingTechniques
{
    class Program
    {
        static void Main(string[] args)
        {
            Program ob = new Program();
            //Create an array and initialize it 
            int[] search_list = new int[] { 3, 1, 9, 8, 7, 12, 56, 23, 89 };

            int n, result;
            //Read the target value to search
            Console.WriteLine("Enter a value to search: ");
            n = Int32.Parse(Console.ReadLine());
            result = ob.LinearSearch(search_list, n);
            if (n != -1)
                Console.WriteLine("The target value " + n + " is found at position " + result);
            else
                Console.WriteLine("Target not found!");

        }

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

Output:

Linear Search Demo
Linear Search Demo

Binary Search

This searching technique requires the list of elements to be sorted. Hence, here we use the Sort() method of Array class to sort the array before passing it to the function search_vale(). Further, this function computes the mid-value of the index range and compares it with the target element, and updates this mid-value according to the method described earlier. Here also the index of the target element is returned if it is present in the array or -1 is returned otherwise.

using System;
namespace BinarySearch
{
    class Program
    {
        static void Main(string[] args)
        {
            Program ob = new Program();
            //Create an array and initialize it 
            int[] search_list = new int[] { 3, 1, 9, 8, 7, 12, 56, 23, 89 };

            int n, result;

            //Display the array elements
            Console.WriteLine("Array Elements: ");
            foreach (int x in search_list) Console.Write(x + " ");
            Console.WriteLine();

            //Sort the array
            Array.Sort(search_list);
            Console.WriteLine("Sorted Array: ");
            foreach (int x in search_list) Console.Write(x + " ");
            Console.WriteLine();

            //Read the target value to search
            Console.WriteLine("Enter a value to search: ");
            n = Int32.Parse(Console.ReadLine());
            result = ob.search_value(search_list, n);
            if (result != -1)
                Console.WriteLine("The target value " + n + " is found at position " + (result+1));
            else
                Console.WriteLine("Target not found!");
        }
        int search_value(int[] arr, int target)
        {
            int low, high, mid;
            low = 0;
            high = arr.Length - 1;
            mid = (low + high) / 2;
            while(low<=high)
            {
                if (arr[mid] == target)
                    return mid + 1;
                else
                    if (target < arr[mid])
                        high = mid - 1;
                else
                    low = mid + 1;
                mid = (low + high) / 2;
            }
            return -1;
        }
    }
}

Output:

Binary Search Demo
Binary Search Demo

Summary

The Linear Search and Binary Search techniques are useful in many computer science applications. Hence their efficient implementation is crucial in such applications. Basically, the linear search is a simple method to implement and can be useful where the list is not too long. However, as the size of the list grows, a more efficient searching technique such as binary search is more useful.


Related Topics

Creating Jagged Arrays in C#

Learning Indexers in C#

Understanding Method Parameter Modifiers in C#

Leave a Comment

Your email address will not be published. Required fields are marked *