Lab Sheet 3: Binary Search & Sorting

DSA Programming Solutions | Instructor: Prof. N L Bhanu Murthy

Authors

PARTH MUNJAL

AKARSH JAIN

Published

March 30, 2026

Q1: Student Ranking with Tie Handling

Description: Sort students based on Higher Marks, and then by Smaller Submission Delay.

Sample Input

Sample Output

Solution

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int marks;
    int delay;
} Student;

int compare(const void* a, const void* b) {
    Student* s1 = (Student*)a;
    Student* s2 = (Student*)b;
    if (s1->marks != s2->marks) return s2->marks - s1->marks;
    return s1->delay - s2->delay;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    Student *students = (Student*)malloc(n * sizeof(Student));
    for (int i = 0; i < n; i++) scanf("%d %d", &students[i].marks, &students[i].delay);
    
    qsort(students, n, sizeof(Student), compare);
    for (int i = 0; i < n; i++) printf("%d %d\n", students[i].marks, students[i].delay);
    free(students);
    return 0;
}

Q2: Peak Element in an Array

Description: Find an index of any single peak element using Binary Search.

Sample Input

6
-3 -10 -2 -5 -6 1

Sample Output

Solution

#include <stdio.h>
#include <stdlib.h>

int findPeak(int arr[], int n) {
    int low = 0, high = n - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < arr[mid + 1]) low = mid + 1;
        else high = mid;
    }
    return low;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    int *arr = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    printf("%d\n", findPeak(arr, n));
    free(arr);
    return 0;
}

Q3: Minimum Eating Speed

Description: Minimum integer speed X to finish N piles of snacks within H hours.

Sample Input

4 8
3 6 7 11

Sample Output

Solution

#include <stdio.h>
#include <stdlib.h>

int canFinish(int piles[], int n, int speed, int h) {
    long hours = 0;
    for (int i = 0; i < n; i++) {
        hours += (piles[i] + speed - 1) / speed;
    }
    return hours <= h;
}

int minEatingSpeed(int piles[], int n, int h) {
    int maxPile = 0;
    for(int i=0; i<n; i++) if(piles[i] > maxPile) maxPile = piles[i];
    int low = 1, high = maxPile;
    int ans = high;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canFinish(piles, n, mid, h)) {
            ans = mid;
            high = mid - 1;
        } else low = mid + 1;
    }
    return ans;
}

int main() {
    int n, h;
    if (scanf("%d %d", &n, &h) != 2) return 1;
    int *piles = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &piles[i]);
    printf("%d\n", minEatingSpeed(piles, n, h));
    free(piles);
    return 0;
}

Q4: Search in Rotated Sorted Array

Description: Search for a target in a rotated sorted array using Binary Search.

Sample Input

7
4 5 6 -3 -2 0 2
-2

Sample Output

Solution

#include <stdio.h>
#include <stdlib.h>

int searchRotated(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        if (arr[low] <= arr[mid]) {
            if (target >= arr[low] && target < arr[mid]) high = mid - 1;
            else low = mid + 1;
        } else {
            if (target > arr[mid] && target <= arr[high]) low = mid + 1;
            else high = mid - 1;
        }
    }
    return -1;
}

int main() {
    int n, target;
    if (scanf("%d", &n) != 1) return 1;
    int *arr = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    if (scanf("%d", &target) != 1) { free(arr); return 1; }
    printf("%d\n", searchRotated(arr, n, target));
    free(arr);
    return 0;
}

Q5: Find First and Last Occurrence

Description: Find starting and ending index of a target in a sorted array.

Sample Input

6
1 2 4 4 4 5
4

Sample Output

2 4

Solution

#include <stdio.h>
#include <stdlib.h>

int findBoundary(int arr[], int n, int target, int first) {
    int low = 0, high = n - 1, res = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            res = mid;
            if (first) high = mid - 1;
            else low = mid + 1;
        } else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return res;
}

int main() {
    int n, target;
    if (scanf("%d", &n) != 1) return 1;
    int *arr = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    if (scanf("%d", &target) != 1) { free(arr); return 1; }
    printf("%d %d\n", findBoundary(arr, n, target, 1), findBoundary(arr, n, target, 0));
    free(arr);
    return 0;
}

Q6: Equation Solver

Description: Find largest x such that 2x^3 - x^2 + 5x \le Y.

Sample Input

Sample Output

Solution

#include <stdio.h>

long long f(long long x) {
    return 2 * x * x * x - x * x + 5 * x;
}

int main() {
    long long y;
    if (scanf("%lld", &y) != 1) return 1;
    long long low = 0, high = 1e6, ans = 0;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (f(mid) <= y) {
            ans = mid;
            low = mid + 1;
        } else high = mid - 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Q7: Group Sorting

Description: Divide array into groups of strictly increasing sizes (1, 2, 3…) and sort each.

Sample Input

10
10 9 8 7 6 5 4 3 2 1

Sample Output

10 8 9 5 6 7 1 2 3 4

Solution

#include <stdio.h>
#include <stdlib.h>

int comp(const void *a, const void *b) { return *(int*)a - *(int*)b; }

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    int *arr = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    int current = 0, size = 1;
    while (current < n) {
        int len = (current + size <= n) ? size : (n - current);
        qsort(&arr[current], len, sizeof(int), comp);
        current += len;
        size++;
    }
    for (int i = 0; i < n; i++) printf("%d%s", arr[i], (i == n - 1) ? "" : " ");
    printf("\n");
    free(arr);
    return 0;
}

Q8: The Logistics Manager

Description: Minimum ship capacity to transport N packages in D days.

Sample Input

5 2
1 2 3 4 5

Sample Output

Solution

#include <stdio.h>
#include <stdlib.h>

int canShip(int w[], int n, int cap, int d) {
    int days = 1, current = 0;
    for (int i = 0; i < n; i++) {
        if (w[i] > cap) return 0;
        if (current + w[i] > cap) {
            days++;
            current = w[i];
        } else current += w[i];
    }
    return days <= d;
}

int minCapacity(int w[], int n, int d) {
    int low = 0, high = 0;
    for (int i = 0; i < n; i++) {
        if (w[i] > low) low = w[i];
        high += w[i];
    }
    int ans = high;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canShip(w, n, mid, d)) {
            ans = mid;
            high = mid - 1;
        } else low = mid + 1;
    }
    return ans;
}

int main() {
    int n, d;
    if (scanf("%d %d", &n, &d) != 2) return 1;
    int *w = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &w[i]);
    printf("%d\n", minCapacity(w, n, d));
    free(w);
    return 0;
}

Q9: Inversion Count

Description: Count inversions using Merge Sort.

Sample Input

5
2 4 1 3 5

Sample Output

Solution

#include <stdio.h>
#include <stdlib.h>

long long merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid, k = left;
    long long count = 0;
    while (i <= mid - 1 && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else {
            temp[k++] = arr[j++];
            count += (mid - i);
        }
    }
    while (i <= mid - 1) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (i = left; i <= right; i++) arr[i] = temp[i];
    return count;
}

long long mergeSort(int arr[], int temp[], int left, int right) {
    long long count = 0;
    if (right > left) {
        int mid = (right + left) / 2;
        count += mergeSort(arr, temp, left, mid);
        count += mergeSort(arr, temp, mid + 1, right);
        count += merge(arr, temp, left, mid + 1, right);
    }
    return count;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    int *arr = (int *)malloc(n * sizeof(int));
    int *temp = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    printf("%lld\n", mergeSort(arr, temp, 0, n - 1));
    free(arr); free(temp);
    return 0;
}

Q10: The Median Merger

Description: Find Median of two sorted arrays combined using Binary Search.

Sample Input

5
1 4 7 10 12
6
2 3 6 8 9 11

Sample Output

7.00

Solution

#include <stdio.h>
#include <stdlib.h>

double findMedian(int nums1[], int n, int nums2[], int m) {
    if (n > m) return findMedian(nums2, m, nums1, n);
    int low = 0, high = n;
    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (n + m + 1) / 2 - partitionX;
        
        int maxLeftX = (partitionX == 0) ? -2e9 : nums1[partitionX - 1];
        int minRightX = (partitionX == n) ? 2e9 : nums1[partitionX];
        
        int maxLeftY = (partitionY == 0) ? -2e9 : nums2[partitionY - 1];
        int minRightY = (partitionY == m) ? 2e9 : nums2[partitionY];
        
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((n + m) % 2 == 0)
                return (double)( (maxLeftX > maxLeftY ? maxLeftX : maxLeftY) + (minRightX < minRightY ? minRightX : minRightY) ) / 2.0;
            else
                return (double)(maxLeftX > maxLeftY ? maxLeftX : maxLeftY);
        } else if (maxLeftX > minRightY) high = partitionX - 1;
        else low = partitionX + 1;
    }
    return 0.0;
}

int main() {
    int n, m;
    if (scanf("%d", &n) != 1) return 1;
    int *nums1 = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &nums1[i]);
    if (scanf("%d", &m) != 1) { free(nums1); return 1; }
    int *nums2 = (int *)malloc(m * sizeof(int));
    for (int i = 0; i < m; i++) scanf("%d", &nums2[i]);
    
    printf("%.2f\n", findMedian(nums1, n, nums2, m));
    free(nums1); free(nums2);
    return 0;
}

--- title: "Lab Sheet 3: Binary Search & Sorting" subtitle: "DSA Programming Solutions | Instructor: Prof. N L Bhanu Murthy" author: - "PARTH MUNJAL" - "AKARSH JAIN" date: last-modified format: html: toc: true toc-depth: 3 code-tools: true number-sections: false theme: cosmo robots: noindex --- # Q1: Student Ranking with Tie Handling **Description:** Sort students based on Higher Marks, and then by Smaller Submission Delay. ::: {.callout-note title="Sample Input"} ``` 4 80 4 90 5 85 2 80 3 ``` ::: ::: {.callout-note title="Sample Output"} ``` 90 5 85 2 80 3 80 4 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> typedef struct { int marks; int delay; } Student; int compare(const void* a, const void* b) { Student* s1 = (Student*)a; Student* s2 = (Student*)b; if (s1->marks != s2->marks) return s2->marks - s1->marks; return s1->delay - s2->delay; } int main() { int n; if (scanf("%d", &n) != 1) return 1; Student *students = (Student*)malloc(n * sizeof(Student)); for (int i = 0; i < n; i++) scanf("%d %d", &students[i].marks, &students[i].delay); qsort(students, n, sizeof(Student), compare); for (int i = 0; i < n; i++) printf("%d %d\n", students[i].marks, students[i].delay); free(students); return 0; } ``` ::: # Q2: Peak Element in an Array **Description:** Find an index of any single peak element using Binary Search. ::: {.callout-note title="Sample Input"} ``` 6 -3 -10 -2 -5 -6 1 ``` ::: ::: {.callout-note title="Sample Output"} ``` 0 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int findPeak(int arr[], int n) { int low = 0, high = n - 1; while (low < high) { int mid = low + (high - low) / 2; if (arr[mid] < arr[mid + 1]) low = mid + 1; else high = mid; } return low; } int main() { int n; if (scanf("%d", &n) != 1) return 1; int *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); printf("%d\n", findPeak(arr, n)); free(arr); return 0; } ``` ::: # Q3: Minimum Eating Speed **Description:** Minimum integer speed $X$ to finish $N$ piles of snacks within $H$ hours. ::: {.callout-note title="Sample Input"} ``` 4 8 3 6 7 11 ``` ::: ::: {.callout-note title="Sample Output"} ``` 4 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int canFinish(int piles[], int n, int speed, int h) { long hours = 0; for (int i = 0; i < n; i++) { hours += (piles[i] + speed - 1) / speed; } return hours <= h; } int minEatingSpeed(int piles[], int n, int h) { int maxPile = 0; for(int i=0; i<n; i++) if(piles[i] > maxPile) maxPile = piles[i]; int low = 1, high = maxPile; int ans = high; while (low <= high) { int mid = low + (high - low) / 2; if (canFinish(piles, n, mid, h)) { ans = mid; high = mid - 1; } else low = mid + 1; } return ans; } int main() { int n, h; if (scanf("%d %d", &n, &h) != 2) return 1; int *piles = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &piles[i]); printf("%d\n", minEatingSpeed(piles, n, h)); free(piles); return 0; } ``` ::: # Q4: Search in Rotated Sorted Array **Description:** Search for a target in a rotated sorted array using Binary Search. ::: {.callout-note title="Sample Input"} ``` 7 4 5 6 -3 -2 0 2 -2 ``` ::: ::: {.callout-note title="Sample Output"} ``` 4 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int searchRotated(int arr[], int n, int target) { int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) return mid; if (arr[low] <= arr[mid]) { if (target >= arr[low] && target < arr[mid]) high = mid - 1; else low = mid + 1; } else { if (target > arr[mid] && target <= arr[high]) low = mid + 1; else high = mid - 1; } } return -1; } int main() { int n, target; if (scanf("%d", &n) != 1) return 1; int *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); if (scanf("%d", &target) != 1) { free(arr); return 1; } printf("%d\n", searchRotated(arr, n, target)); free(arr); return 0; } ``` ::: # Q5: Find First and Last Occurrence **Description:** Find starting and ending index of a target in a sorted array. ::: {.callout-note title="Sample Input"} ``` 6 1 2 4 4 4 5 4 ``` ::: ::: {.callout-note title="Sample Output"} ``` 2 4 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int findBoundary(int arr[], int n, int target, int first) { int low = 0, high = n - 1, res = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { res = mid; if (first) high = mid - 1; else low = mid + 1; } else if (arr[mid] < target) low = mid + 1; else high = mid - 1; } return res; } int main() { int n, target; if (scanf("%d", &n) != 1) return 1; int *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); if (scanf("%d", &target) != 1) { free(arr); return 1; } printf("%d %d\n", findBoundary(arr, n, target, 1), findBoundary(arr, n, target, 0)); free(arr); return 0; } ``` ::: # Q6: Equation Solver **Description:** Find largest $x$ such that $2x^3 - x^2 + 5x \le Y$. ::: {.callout-note title="Sample Input"} ``` 200 ``` ::: ::: {.callout-note title="Sample Output"} ``` 4 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> long long f(long long x) { return 2 * x * x * x - x * x + 5 * x; } int main() { long long y; if (scanf("%lld", &y) != 1) return 1; long long low = 0, high = 1e6, ans = 0; while (low <= high) { long long mid = low + (high - low) / 2; if (f(mid) <= y) { ans = mid; low = mid + 1; } else high = mid - 1; } printf("%lld\n", ans); return 0; } ``` ::: # Q7: Group Sorting **Description:** Divide array into groups of strictly increasing sizes (1, 2, 3...) and sort each. ::: {.callout-note title="Sample Input"} ``` 10 10 9 8 7 6 5 4 3 2 1 ``` ::: ::: {.callout-note title="Sample Output"} ``` 10 8 9 5 6 7 1 2 3 4 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int comp(const void *a, const void *b) { return *(int*)a - *(int*)b; } int main() { int n; if (scanf("%d", &n) != 1) return 1; int *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); int current = 0, size = 1; while (current < n) { int len = (current + size <= n) ? size : (n - current); qsort(&arr[current], len, sizeof(int), comp); current += len; size++; } for (int i = 0; i < n; i++) printf("%d%s", arr[i], (i == n - 1) ? "" : " "); printf("\n"); free(arr); return 0; } ``` ::: # Q8: The Logistics Manager **Description:** Minimum ship capacity to transport $N$ packages in $D$ days. ::: {.callout-note title="Sample Input"} ``` 5 2 1 2 3 4 5 ``` ::: ::: {.callout-note title="Sample Output"} ``` 9 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int canShip(int w[], int n, int cap, int d) { int days = 1, current = 0; for (int i = 0; i < n; i++) { if (w[i] > cap) return 0; if (current + w[i] > cap) { days++; current = w[i]; } else current += w[i]; } return days <= d; } int minCapacity(int w[], int n, int d) { int low = 0, high = 0; for (int i = 0; i < n; i++) { if (w[i] > low) low = w[i]; high += w[i]; } int ans = high; while (low <= high) { int mid = low + (high - low) / 2; if (canShip(w, n, mid, d)) { ans = mid; high = mid - 1; } else low = mid + 1; } return ans; } int main() { int n, d; if (scanf("%d %d", &n, &d) != 2) return 1; int *w = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &w[i]); printf("%d\n", minCapacity(w, n, d)); free(w); return 0; } ``` ::: # Q9: Inversion Count **Description:** Count inversions using Merge Sort. ::: {.callout-note title="Sample Input"} ``` 5 2 4 1 3 5 ``` ::: ::: {.callout-note title="Sample Output"} ``` 3 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> long long merge(int arr[], int temp[], int left, int mid, int right) { int i = left, j = mid, k = left; long long count = 0; while (i <= mid - 1 && j <= right) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else { temp[k++] = arr[j++]; count += (mid - i); } } while (i <= mid - 1) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (i = left; i <= right; i++) arr[i] = temp[i]; return count; } long long mergeSort(int arr[], int temp[], int left, int right) { long long count = 0; if (right > left) { int mid = (right + left) / 2; count += mergeSort(arr, temp, left, mid); count += mergeSort(arr, temp, mid + 1, right); count += merge(arr, temp, left, mid + 1, right); } return count; } int main() { int n; if (scanf("%d", &n) != 1) return 1; int *arr = (int *)malloc(n * sizeof(int)); int *temp = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); printf("%lld\n", mergeSort(arr, temp, 0, n - 1)); free(arr); free(temp); return 0; } ``` ::: # Q10: The Median Merger **Description:** Find Median of two sorted arrays combined using Binary Search. ::: {.callout-note title="Sample Input"} ``` 5 1 4 7 10 12 6 2 3 6 8 9 11 ``` ::: ::: {.callout-note title="Sample Output"} ``` 7.00 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> double findMedian(int nums1[], int n, int nums2[], int m) { if (n > m) return findMedian(nums2, m, nums1, n); int low = 0, high = n; while (low <= high) { int partitionX = (low + high) / 2; int partitionY = (n + m + 1) / 2 - partitionX; int maxLeftX = (partitionX == 0) ? -2e9 : nums1[partitionX - 1]; int minRightX = (partitionX == n) ? 2e9 : nums1[partitionX]; int maxLeftY = (partitionY == 0) ? -2e9 : nums2[partitionY - 1]; int minRightY = (partitionY == m) ? 2e9 : nums2[partitionY]; if (maxLeftX <= minRightY && maxLeftY <= minRightX) { if ((n + m) % 2 == 0) return (double)( (maxLeftX > maxLeftY ? maxLeftX : maxLeftY) + (minRightX < minRightY ? minRightX : minRightY) ) / 2.0; else return (double)(maxLeftX > maxLeftY ? maxLeftX : maxLeftY); } else if (maxLeftX > minRightY) high = partitionX - 1; else low = partitionX + 1; } return 0.0; } int main() { int n, m; if (scanf("%d", &n) != 1) return 1; int *nums1 = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &nums1[i]); if (scanf("%d", &m) != 1) { free(nums1); return 1; } int *nums2 = (int *)malloc(m * sizeof(int)); for (int i = 0; i < m; i++) scanf("%d", &nums2[i]); printf("%.2f\n", findMedian(nums1, n, nums2, m)); free(nums1); free(nums2); return 0; } ``` :::