Commonly used Algorithms

Question 1

Binary Search

Answer 1

Binary Search is a divide-and-conquer algorithm that efficiently searches a sorted array by repeatedly dividing the search interval in half.

Algorithm:

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

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

return -1; // not found }

When to Use: Use Binary Search when you have a sorted collection and need to quickly find an element.

Question 2

Depth-First Search (DFS)

Answer 2

Description: DFS is a graph traversal algorithm where you go as deep as possible down one path before backing up and trying a different one.

Algorithm (Recursive):

void DFS(Node node, HashSet<Node> visited) {
visited.Add(node);</Node>

foreach (var neighbor in node.neighbors) {
    if (!visited.Contains(neighbor)) {
        DFS(neighbor, visited);
    }
} }

When to Use: Use DFS to explore all paths in a graph, especially useful for traversal and finding connected components.

Question 3

Breadth-First Search (BFS)

Answer 3

Description: BFS is a graph traversal algorithm that explores all neighbors at the present depth level before moving on to nodes at the next depth level.

Algorithm:

void BFS(Node start) {
Queue<Node> queue = new Queue<Node>();
HashSet<Node> visited = new HashSet<Node>();</Node></Node></Node></Node>

queue.Enqueue(start);
visited.Add(start);

while (queue.Count > 0) {
    Node node = queue.Dequeue();
    
    foreach (var neighbor in node.neighbors) {
        if (!visited.Contains(neighbor)) {
            queue.Enqueue(neighbor);
            visited.Add(neighbor);
        }
    }
} }

When to Use: Use BFS for shortest path finding in unweighted graphs or when you need to visit all nodes level by level.

Question 4

Merge Sort

Answer 4

Description: Merge Sort is a divide-and-conquer algorithm that recursively divides an array into halves, sorts them, and then merges the sorted halves.

Algorithm:

void MergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}

void Merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;

while (i <= mid && j <= right) {
    if (arr[i] <= arr[j])
        temp[k++] = arr[i++];
    else
        temp[k++] = arr[j++];
}

while (i <= mid)
    temp[k++] = arr[i++];

while (j <= right)
    temp[k++] = arr[j++];

for (i = left, k = 0; i <= right; i++, k++)
    arr[i] = temp[k]; }

When to Use: Use Merge Sort for sorting arrays efficiently, especially when stability and guaranteed O(n log n) time complexity are required.

Question 5

Quicksort

Answer 5

Description: Quicksort is a divide-and-conquer algorithm that partitions an array into smaller arrays based on a pivot element, and recursively sorts the partitions.

Algorithm:

void Quicksort(int[] arr, int left, int right) {
if (left < right) {
int pivot = Partition(arr, left, right);
Quicksort(arr, left, pivot - 1);
Quicksort(arr, pivot + 1, right);
}
}

int Partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;

for (int j = left; j < right; j++) {
    if (arr[j] < pivot) {
        i++;
        Swap(arr, i, j);
    }
}

Swap(arr, i + 1, right);
return i + 1; }

void Swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

When to Use: Use Quicksort for in-place sorting with average O(n log n) time complexity. It’s efficient for large datasets.