Introduction to Programming in C

📘 Searching and Sorting Algorithms in C (Binary Search, Merge Sort, Quick Sort)

Searching and sorting are essential to data processing and algorithm optimization. In this chapter, we’ll learn how to implement Binary Search for efficient searching, and two powerful sorting algorithms — Merge Sort and Quick Sort.

🔍 Binary Search

A fast search algorithm that works on sorted arrays. It divides the array into halves until the desired value is found.

int binarySearch(int arr[], int n, int key) {
  int left = 0, right = n - 1;
  while (left <= right) {
    int mid = (left + right) / 2;
    if (arr[mid] == key)
      return mid;
    else if (arr[mid] < key)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return -1;
}

⚙️ Time Complexity:

• Best case: O(1)
• Average/Worst case: O(log n)

🔃 Merge Sort

Merge Sort is a divide-and-conquer algorithm. It recursively divides the array and then merges sorted halves.

void merge(int arr[], int l, int m, int r) {
  int n1 = m - l + 1;
  int n2 = r - m;
  int L[n1], R[n2];

  for (int i = 0; i < n1; i++) L[i] = arr[l + i];
  for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

  int i = 0, j = 0, k = l;
  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) arr[k++] = L[i++];
    else arr[k++] = R[j++];
  }

  while (i < n1) arr[k++] = L[i++];
  while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
  }
}

⚙️ Time Complexity:

• Best/Average/Worst: O(n log n)

⚡ Quick Sort

Quick Sort picks a pivot and partitions the array around it. Faster in practice than Merge Sort for many cases.

int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = (low - 1);

  for (int j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }
  }
  int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
  return (i + 1);
}

void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

⚙️ Time Complexity:

• Best/Average: O(n log n)
• Worst: O(n²) (when pivot is smallest/largest repeatedly)

📚 UdaanPath Example

Suppose UdaanPath stores student scores. You can use Merge Sort to sort them by performance, and Binary Search to find a student with a specific score quickly.

📝 Practice Tasks

1. Implement Binary Search on a sorted array
2. Apply Merge Sort on an array of 10 elements
3. Use Quick Sort to sort an array of student roll numbers
4. Compare output and speed for Merge vs Quick Sort

✅ Summary

• Binary Search offers fast lookup in sorted arrays
• Merge Sort is stable and consistent in performance
• Quick Sort is efficient in most practical cases
• Sorting is essential for data organization, searching, and ranking

🚀 Coming Next

In the next chapter, we’ll analyze Time and Space Complexity for C programs — helping you understand the performance and optimization of your code.