🚀 DSA with C – Day 3: Bubble Sort & Binary Search

 

🎯 Goal:

• Learn Bubble Sort and sort arrays.

• Understand how Binary Search works.

• Compare Linear vs Binary Search.

• Practice problems on sorted arrays.

---

🧠 Theory

✅ Bubble Sort:

• Repeatedly compares adjacent elements and swaps them if they’re in the wrong order.

• Worst-case time complexity: O(n²)

• Best-case (already sorted): O(n) with optimization

---

👨‍💻 Bubble Sort in C

#include <stdio.h>

int main() {
    int arr[100], n, i, j, temp;

    printf("Enter number of elements: ");
    scanf("%d", &n);
    printf("Enter %d elements:\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    // Bubble Sort
    for (i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (swapped == 0)
            break; // Already sorted
    }

    printf("Sorted array:\n");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

---

✅ Binary Search:

• Efficient searching technique on sorted arrays.

• Time Complexity: O(log n)

• Repeatedly divide the array and compare with middle element.

---

👨‍💻 Binary Search in C

#include <stdio.h>

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1, mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1; // Not found
}

int main() {
    int arr[100], n, key;

    printf("Enter number of elements: ");
    scanf("%d", &n);
    printf("Enter %d sorted elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Enter element to search: ");
    scanf("%d", &key);

    int result = binarySearch(arr, n, key);
    if (result == -1)
        printf("Element not found.\n");
    else
        printf("Element found at index %d.\n", result);

    return 0;
}

---

🔁 Linear vs Binary Search

Feature	Linear Search	Binary Search
Time Complexity	O(n)	O(log n)
Sorted Array Required	❌ No	✅ Yes
Speed	Slower	Faster for large data
Approach	Scan all elements	Divide & Conquer

🧪 Practice Problems:

1. Sort an array using Bubble Sort in descending order.

2. Count how many swaps were done during Bubble Sort.

3. Use Binary Search to find the number of occurrences of a given element.

4. If not found in Binary Search, return where it should be inserted.

---

📘 Homework for Day 3:

• Implement recursive Binary Search.

• Write a program that first sorts using Bubble Sort and then searches using Binary Search.

• LeetCode problem suggestion: Search Insert Position

---

📅 Day 3 Summary

• ✅ Learned Bubble Sort (with optimization)

• ✅ Implemented Binary Search (iterative)

• ✅ Practiced comparing search algorithms