Location>code7788 >text

Four classic lookup algorithms common to C#

Popularity:900 ℃/2024-10-24 13:15:00

preamble

In programming, data structures and algorithms are the cornerstones for building efficient, reliable and scalable software systems. They play a crucial role in improving program performance, optimizing resource utilization, and solving complex problems. Today Dajao shares four common classic lookup algorithms in C#.

  • A practical beginner's guide to C# data structures and algorithms: /s/XPRmwWmoZa4zq29Kx-u4HA
  • Welcome to the DotNetGuide Technical Community Networking Group: /s/07UYvW8uuspWaaBrWjw2MQ

C# Binary Lookup Algorithm

synopsis

The binary lookup algorithm is a search algorithm that finds a specific element in an ordered array.

  • Detailed Article Description: /s/uCuqv0zOI0ZsF48Q1LoCsQ

code implementation

public class Dichotomous Lookup Algorithm
    {
        /// <summary>
/// Dichotomous lookup algorithm
        /// </summary>
        /// <param name="arr"> arr is the sorted array </param>
        /// <param name="target"> target is the target value to look up </param>
/// <returns> the index of the target value in the array, or -1 if not found</returns>.
        public static int BinarySearch(int[] arr, int target)
        {
int left = 0; // define left pointer
int right = - 1; // define right pointer

            while (left <= right)
            {
// Calculate the index of the middle element
                int mid = left + (right - left) / 2;

                if (arr[mid] == target)
                {
// If the middle element is equal to the target value
                    return mid; // find successful, return index
                }
                else if (arr[mid] < target)
                {
// if the target value is less than the middle element, lookup in the left half
                    left = mid + 1;
                }
                else
                {
// if the target value is greater than the middle element, lookup in the right half
                    right = mid - 1;
                }
            }

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

        public static void BinarySearchRun()
        {
int[] arr = { 1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 }; //note: the array here is a sorted array
int target = 31; //need to find the target value

int result = BinarySearch(arr, target); //call binary search method

            if (result == -1)
            {
                ("Element not found").
            }
            else
            {
                ($"Element found with index: {result} and value: {arr[result]}");;
            }
        }
    }

C# Linear Lookup Algorithm

synopsis

Linear lookup algorithm is a simple lookup algorithm used to find a specific element in an array or list. It starts from the first element of the array and checks each element one by one until it finds the desired element or searches the entire array. The time complexity of linear lookup is O(n), where n is the number of elements in the array.

  • Detailed Article Description: /s/VKC5lEYCL7SHieNMaPOE3A

code implementation

  public static void LinearSearchRun()
        {
            int[] arr = { 2, 3, 4, 10, 40, 50, 100, 77, 88, 99 };
            int target = 100;

            int result = LinearSearch(arr, target);

// Output results
            if (result == -1)
            {
                ("Element not found").
            }
            else
            {
                ($"Element found at index {result}, index = {result}");
            }
        }

        /// <summary>
/// Linear lookup function
        /// </summary>
        /// <param name="arr">arr</param>
        /// <param name="target">target</param>
        /// <returns></returns>
        public static int LinearSearch(int[] arr, int target)
        {
// Traverse the array
            for (int i = 0; i < ; i++)
            {
// If the target value is found, return its index
                if (arr[i] == target)
                {
                    return i;
                }
            }
// Return -1 if not found
            return -1;
        }

C# Binary Search Tree Algorithm

synopsis

Binary Search Tree (BST) is a binary tree data structure with ordered nodes.

  • Detailed Article Description: /s/qs8CZzjtmyXkQhkRWmqllA

code implementation

namespace HelloDotNetGuide.Common Algorithms
{
public class Binary Search Tree Algorithm
    {
        public static void BinarySearchTreeRun()
        {
            var bst = new BinarySearchTree();

// Insert some values into the tree
            (50);
            (30);
            (20);
            (40);
            (70);
            (60);
            (80);
            (750);

            ("Medium order traversal (print ordered array):").
            ();

            ("\n");

// Finding certain values
            ("Search for 40: " + (40)); // Output: True
            ("Search for 25: " + (25)); // Output: False

            ("\n");

// Delete a value
            (50);
            ("After deleting 50:").
            ();
        }
    }

    /// <summary>
/// Define the node structure of a binary search tree.
    /// </summary>
    public class TreeNode
    {
        public int Value;
        public TreeNode Left;
        public TreeNode Right;

        public TreeNode(int value)
        {
            Value = value;
            Left = null;
            Right = null;
        }
    }

    /// <summary>
/// Define the binary search tree class
    /// </summary>
    public class BinarySearchTree
    {
        private TreeNode root;

        public BinarySearchTree()
        {
            root = null;
        }

        #region Insert node

        /// <summary>
/// Insert the new value into the binary search tree.
        /// </summary>
        /// <param name="value">value</param>
        public void Insert(int value)
        {
            if (root == null)
            {
                root = new TreeNode(value);
            }
            else
            {
                InsertRec(root, value);
            }
        }

        private void InsertRec(TreeNode node, int value)
        {
            if (value < )
            {
                if ( == null)
                {
                     = new TreeNode(value);
                }
                else
                {
                    InsertRec(, value);
                }
            }
            else if (value > )
            {
                if ( == null)
                {
                     = new TreeNode(value);
                }
                else
                {
                    InsertRec(, value);
                }
            }
            else
            {
//value already exists in the tree, no more insertions
                return;
            }
        }

        #endregion

        #region Find node

        /// <summary>
/// Finds if a value exists in a binary search tree.
        /// </summary>
        /// <param name="value">value</param>
        /// <returns></returns>
        public bool Search(int value)
        {
            return SearchRec(root, value);
        }

        private bool SearchRec(TreeNode node, int value)
        {
// If the current node is empty, the target value was not found
            if (node == null)
            {
                return false;
            }

// If the target value is found, returntrue
            if ( == value)
            {
                return true;
            }

// Recursively find left or right subtree
            if (value < )
            {
                return SearchRec(, value);
            }
            else
            {
                return SearchRec(, value);
            }
        }

        #endregion

        #region Middle-order traversal

        /// <summary>
/// Intermediate order traversal (prints an ordered array)
        /// </summary>
        public void InorderTraversal()
        {
            InorderTraversalRec(root);
        }

        private void InorderTraversalRec(TreeNode root)
        {
            if (root != null)
            {
                InorderTraversalRec();
                ();
                InorderTraversalRec();
            }
        }

        #endregion

        #region Delete node

        /// <summary>
/// Delete a value
        /// </summary>
        /// <param name="val">val</param>
        public void Delete(int val)
        {
            root = DeleteNode(root, val);
        }

        private TreeNode DeleteNode(TreeNode node, int val)
        {
            if (node == null)
            {
                return null;
            }

            if (val < )
            {
                 = DeleteNode(, val);
            }
            else if (val > )
            {
                 = DeleteNode(, val);
            }
            else
            {
// The node has two children
                if ( != null &&  != null)
                {
// Replace the current node with the smallest node in the right subtree
                    TreeNode minNode = FindMin();
                     = ;
                     = DeleteNode(, );
                }
// The node has one child or no children.
                else
                {
                    TreeNode? temp =  != null ?  : ;
                    node = temp;
                }
            }

            return node;
        }

        /// <summary>
/// Find the smallest node in the tree
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private TreeNode FindMin(TreeNode node)
        {
            while ( != null)
            {
                node = ;
            }
            return node;
        }

        #endregion
    }
}

C# Hash Lookup Algorithm

synopsis

Hash lookup algorithm is an efficient lookup algorithm that enables fast access by mapping keys to locations in a hash table. In C#, hash lookups are usually implemented through a Hashtable or Dictionary.

  • Detailed Article Description: /s/WaXCFshzuqVQD6YX2Kcw5g

code implementation

 public class hash lookup algorithm
    {
        /// <summary>
/// Hash lookup function
        /// </summary>
        /// <param name="target">target</param>
        public static void HashSearchFunctionRun(int target)
        {
// Create a dictionary to store key-value pairs
            var dic = new Dictionary<int, string>();
            (1, "one");
            (2, "two");
            (3, "three");

// Find out if the target value exists in the Dictionary.
The //TryGetValue method can return a bool value and the value, if the target value is found, of thetrue and the corresponding value; otherwise, returnsfalse and default values
            string value;
            if ((target, out value))
            {
                ("Found Data: " + value);
            }
            else
            {
                ("Not Found Data.");
            }
        }
    }