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.");
}
}
}