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!
SOCIAL SHARE CARD GENERATOR