The Pursuit of Knowledge
Alright, let's be real here. The best way to learn "difficult" concepts (well actually they're not actually that scary until you get exposure) is to be passionate and embrace being a complete beginner. Also, asking what everyone calls "stupid questions" will actually make you stand out in the long run. Trust me on this one.
I'm not some LeetCode wizard or anything - just a random CS student who's made plenty of mistakes and will continue making(That is just the way it is). And honestly? I don't want you to make the same ones I did.
What The Heck Is Data Structures
Looking at the broader perspective, Data Structures are just chunks of data that are used with algorithms. Nothing much at all, do not overestimate it. Think of algorithms as your smart friends who help you figure out your problems and as a result you get less stressed and tired. Data structures? They're just the organized way you store your data so your algorithms can work their magic.
Diving Into First Data Structure: Array
When i think about arrays , i imagine it as collection of boxes which are in the contiguous memory(are sitting near to each other) and are the same type(in C++ it is) and it is really useful to see the box in a quick way. Its size is fixed which means if we want to add a new a element and we have reached the size , we need to create a new collection of boxes for the sake of adding a new box.
int grades[] = {1,2,3};
int size = sizeof(grades) / sizeof(grades[0]); // divide 12 bytes/4 bytes
//the first element is int and the size is 4
//total size is 12 because we have 3 numbers
//readable iteration
for(int i = 0; i < size;i++){
std::cout << grades[i] << '\n';
}
//weird style
for(int* ptr = grades; ptr < grades + size; ptr++){
std::cout << *ptr << '\n';
}
Look, I get it. Pointers look scary and you might think "this is too low-level, I don't need this." But here's the deal ,understanding this stuff will make you a way smarter developer.
Remember how I said those boxes are sitting right next to each other? Well, that asterisk (*) is like your magic key that lets you peek inside each box. When you just write ptr, you're getting the address. When you write *ptr, you're actually opening the box and seeing what's inside.
Most programming languages do this behind the scenes anyway, so why not understand it instead of treating it like mysterious black box? Plus, pointers are absolute lifesavers for optimization and avoiding unnecessary copying. Your future self will thank you.
Dynamic Array std::vector
std::vector is used to avoid fixed size and increasing the size dynamically. What does dynamic mean? It means that even if we reach the fixed size by adding a new element its capacity will be increased twice.
- Size = how many elements you actually have
- Capacity = how much space is reserved
std::vector<int> dummyVec{1,2,3};
std::cout << "Initial - Size: " << dummyVec.size()
<< ", Capacity: " << dummyVec.capacity() << std::endl;
// Output: Size: 3, Capacity: 3
dummyVec.push_back(4);
std::cout << "After push_back - Size: " << dummyVec.size()
<< ", Capacity: " << dummyVec.capacity() << std::endl;
// Output: Size: 4, Capacity: 6
for(int i = 0; i < dummyVec.size(); i++){
std::cout << dummyVec[i] << '\n';
}
As you see here we did not need to finally find the size manually we found it via method then we iterate it through and push_back(newElement) basically means push to the end of the vector. There are ways of optimizing vector such as using emplace_back(newElement) instead of push_back(newElement) for avoiding copy and using reserve(size) for reserving some memory for us something like booking a table at the restaurant. I will put the materials below which you can check if you are interested in std::vector.
First Challenge
Imagine that we want to find a student who got 100 in the quiz so somehow we need to access the boxes to see the results and imagine that all numbers in the array is sorted in ascending order (10,20,30,40,50,60,70,80,90,100). Wait, we can do it by iterating through array and find it right?
//we use & which is a reference you can think like this as a nickname
//and here is the deal in programming there is one nickname no more
bool search(std::vector<int>&grades,int target = 100){
for(int i = 0; i < grades.size();i++){
if(grades[i] == target){ //if the one of these numbers is equal to target return true
return true;
} //if is going to run 10 times and find 100 in the last one.Always think about worst case scenario. This is called O(n)
}
return false;//unfortunately it did not find there is nobody :(
}
This works, but in the worst case, you'd have to check all 10 grades. That's what we call O(n) - as the number of students grows, the time to search grows proportionally. Not terrible for 10 grades, but imagine searching through 10,000 grades this way!
## Real OG :Binary Search
What the heck is binary search? Instead of checking every single grade, we can look at the middle one and ask: "Is this too high or too low?" Then we throw away half the remaining options and repeat. That is the Deal and in the worst case scenario it will give us O(log n) which we round the number to the ceiling and 4 operations.
bool search(std::vector<int>& grades, int target = 100) {
int low = 0; int high = grades.size()-1;
while(low <= high ){
int mid = low + (high-low)/2;// C++ stuff to avoid integer overflow.
//If you are dealing with small numbers you can use (high+low)/2
if(grades[mid] == target){
return true;
}
if(grades[mid]<target){
low = mid+1;
}
else{
high = mid-1;
}
}
return false;
}
This is exactly what binary search does - it keeps dividing your search space in half until it finds what it's looking for. Pretty cool stuff, right?
When you collect those remainders from bottom to top, you get(if elements are from 1 to 10 and target is 10): 1010 - Bingo! which is 10 in binary!
Try this with other numbers and see the pattern. Math and algorithms are more related than we think!
That's all for Part 1! In the next part, we'll dive into hash sets and hash maps(They have cool names ,but don't worry everything is complicated until you get exposure). Let me know guys ,in the comments if anything was confusing or if you have questions!
Top comments (0)