I'm sure you all have read a quote like this, "First solve the problem, then write the code". At first, I took it lightly. I liked to follow a different approach:"Solving the problem with code".
After coding for a long time, I realized the importance of solving the problem first before jumping into writing code.
In this article, I will try to explain why you should slow down and how can you save your time by slowing down. Also, this will make you a better programmer.
Basics
Let's go back a little. What are computers? Computers are machines that can follow instructions. They are dumb as a chair. They do as we tell them to. We can provide the instructions to the computers, in any programming languages we want. The basics are the same. The computer knows how to execute the code and give us the output. Because the codes we write get translated to a language that the computer understands. It doesn't matter which language you choose, it never mattered. The thing that matters is, can your code do the job or not.
To do the job, we have to give specific instructions to the computer. We know that there are some basic functionalities that every programming language has. For example- loops, variables, conditionals, etc. Every good programmer knows how to use them.
If you have structured the steps you need to follow to accomplish a job, you have already solved the problem. Translating it into a programming language is the easy part.
Examples
Let's try to understand it using some examples. Let's say we are given a sorted array and a target number. We have to return true if the array contains the target number or false if the array doesn't contain the target number.
How should we go about this problem? The first thing that comes to mind is, we can take every element of the array one by one and check it with the target. If it matches we return true. And if after checking all the elements of the array, we don't find a match we return false.
If we write it as an algorithm, it would look like this,
1. Set variable i equal to 0. (Because the first element of the array has index 0)
2. If i is less than the length of the array, go to step-3 Else go to step-4.
3. If array[i] is equal to the target, return true. Else, increment i by 1 and go to step 2.
4. Return false.By writing this algorithm, we have the full picture of how to solve the problem. Now it is just a matter of a few minutes to translate it to your preferred language. There is another way to write algorithms, which resembles the programming languages, called pseudocode.
If we write the above algorithm in pseudocode, it would look like this.
Initialize i equal to 0
while i is less than the array length
if array[i] is equal to the target
return true
Increment i by 1
return false
You may be thinking, for a sorted array checking every element is unnecessary. Yes, you are right. We have a better method to search in a sorted array. That's called binary search. Binary search has a time complexity of O(log n). Our previous solution has a time complexity of O(n) because we are checking every element of the array one by one. So, if the size of the input array increases our code runtime would increase linearly.
I will explain binary search first then I will talk about its time complexity.
Binary Search
What is binary search? It's kind of common sense. Let's take an example. Imagine you went to a hotel to meet a friend. You know the room number your friend is in. Let's say the room number is 7. You go up the stairs and see there are two hallways. One goes to the left and another goes to the right. And you know the hotel rooms are arranged in order from left to right. The middle room you are standing in front of now, which is just beside the staircase has a number 9. You are very sure that you just have to go through the left hallway to reach room number 7.
Notice what you did here. You eliminated half of the possibilities just knowing that the rooms are sorted in order.
We do the same thing when we want to go to a specific page of a book. Nowadays we don't use physical dictionaries or phonebooks. But we used the same technique to find something from the dictionary or a phonebook in the past.
We can use similar logic for searching the number in the array, as the array is already sorted. We can go to the middle number of the array and check if it's equal to or less than or greater than the target. If it's equal to the target we found the number and the program stops. If it's less than our target, we can be sure that our target number cannot be found in the left half of the array. If it's greater than our target, we can be sure that our target number cannot be found in the right half of the array.
Now, what programmers do is just jump into writing codes. They think they have solved the problem. But no, there are missing pieces to our devised algorithm or steps. We have to devise an algorithm that tells the whole process from start to finish. We don't want any missing pieces.
Many programmers get stuck because they think they have figured out the solution. In reality, there are holes in their algorithm. We need a full-proof plan. We have to consider all the edge cases that can happen.
Before we jump into writing code, we have to figure out few things. I always like to take an example of inputs to make a full-proof plan.
Let's say our input array is [3, 5, 6, 7, 9, 11, 12, 13, 15] and the target is 7.
The first thing that comes to my mind is, how can I get the middle element of the array? Or if I am given a starting and ending index value, how can I determine who is the middle value. It's very easy. If we are given start and end index value,
the index of middle value = (start + end) / 2 = ( 0 + 8 ) / 2 = 4
In our example array[4] = 9, we see our target is less than the middle value. From this information, we know for sure that the target can't be in the right portion of the array. So, we set our end index value to the middle value - 1. So, now we have divided our search space in half. On the next iteration, we calculate the middle value again and follow the same steps again. If the middle number is less than the target, we change the start index to the index of the middle number + 1. And if the middle number is greater than the target, we change the end index to the index of the middle number - 1.
In this approach, we are using a loop, but we have to know how to stop the loop. We have to set the condition so that the loop stops after finishing the necessary calculations. Inside the loop, we will have a conditional that checks if the middle value is equal to the target or not. If it's equal to the target, the loop and the program stops there. But if the array doesn't contain the desired value there is no way to stop the loop yet. So, for this edge case, we can use the start and end value of the currently considered list of numbers.
If the start is more than the end index we know for sure that the number doesn't exist in the array.
If we write the pseudocode now,
Initialize start equal to 0
Initialize end equal to array length - 1
while start is less than or equal to end
mid_index equal to (start+end)/2
middle_value equal to array[mid_index]
if middle_value is equal to target
return true
else if middle_value is less than target
start = mid_index + 1
else
end = mid_index - 1
return falseI think now you get the idea. If you can structure the steps necessary to get the job done, coding is the easy part.
Some deep thoughts
This concept of solving problems with well-structured steps is not unique to computer science. In maths, we follow the same approach. We follow some structured steps to tackle a problem. Then we translate it to some mathematical formulas or symbols. We do this in all areas of our life. We determine how to do a task by structuring simple steps. Then we translate the steps to a different language. The language may be maths, programming languages, or any kind of higher-level construct. Under the hood, everything is just simple steps structured in ordered ways.
When you grasp this concept, everything becomes simpler to understand. When you hear someone talking about a theory in physics. You think that you are not smart enough to understand it. But the truth is, you don't know the language of that particular theory.
Time Complexity of Binary Search
Back to the binary search algorithm, what is the time complexity of binary search? As I told you it's O(log n). But why is that?
Have you noticed we divide the input dataset in half after every iteration? So, if you start with 16 elements in the array. After the first iteration, we have 8 elements to think about, then 4, then 2, then 1.
Now, if we take a 2 base logarithm, and calculate the
log(16) = 4, so we can divide the elements into two parts, 4 times.
If the input size was 64, if we take a 2 base logarithm, and calculate the
log(64) = 6, so in the worst case, we just have to divide 6 times to reach the target.
So, we can see the number of operations needed is the 2 base logarithm of the input size n. That's why the time complexity of the binary search is O(log n).
Binary search is a very important algorithm in computer science. It saves us a lot of computing power. But always remember we can only use it in a sorted list of data.
Summary
So, to summarize I can give you some steps to tackle any coding challenges.
- Understand the task fully. What you have to figure out? What data is given?
- Use an example data set to figure out the steps you need to follow.
- Don't leave any missing pieces in your algorithm. Make sure your algorithm makes sense to you fully.
- Apply your algorithm to some data set using pen and paper.
- If you are satisfied, start writing the code.
Thanks for reading this article. I hope you have learned something from it.