Day 44: Competitive Programming Journal

Date: November 5, 2024.
Hello Everyone,

Today marks Day 44 of my competitive programming journey, and I’m here to share my progress.

What I Did Today:
I worked on two problems: Implement binary search to find an element in a sorted array and Count the frequency of each character in a string.

1. Implement binary search to find an element in a sorted array:
Problem:
Given a sorted array and a target element, implement binary search to find its position. If the element is not present, return -1.

Explanation:

• Binary search works by dividing the array into halves repeatedly and comparing the middle element with the target.
• If the middle element equals the target, return its position.
• If the target is smaller, search the left half; otherwise, search the right half.

Here’s the implementation:

int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

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

    return -1;
}

2. Count the frequency of each character in a string:
Problem:
Given a string, count the frequency of each character and display the result.

Explanation:

• Traverse the string and use a frequency array or a map to count the occurrences of each character.
• Print the characters along with their respective frequencies.

Here’s the implementation:

void countCharacterFrequency(const string& str) {
    unordered_map<char, int> freq;

    for (char ch : str) {
        freq[ch]++;
    }

    cout << "Character frequencies:" << endl;
    for (auto& pair : freq) {
        cout << pair.first << ": " << pair.second << endl;
    }
}

Reflection:
Today’s problems were straightforward yet insightful. Implementing binary search refreshed my understanding of the divide-and-conquer approach, while counting character frequencies was a good practice in working with hash maps. Both problems highlighted the importance of optimizing for time complexity.

Stay tuned for more updates, and as always, happy coding!