So, I set myself a bit of a crazy challenge a week ago. I decided to learn Javascript from scratch, and then use it to create a Binary Search Algorithm of a Sorted Array... Simples!
The challenge is from Khan Academy, and it assumes prior knowledge of Javascript. I wasn't going to let that little assumption get in my way! I started off with Codecademy - learned the basics, and then skipped straight to 'for' and 'while' loops.
I thought this would be a good topic for a blog article because I am relatively new to the practice of coding, and I wanted to share my experience with other budding beginners out there. If you are new to programming, or you would like to give programming a go, I hope you find this article interesting and useful.
So, what is an algorithm?
An algorithm is literally just a set of steps that you follow to get something done. Your daily routines are algorithms, for example, getting dressed, going to work, cooking a meal. That's not so intimidating is it!
The first step to coding an algorithm actually requires no coding at all. You just need to work out how to get from A to B. Sketch out the steps that need to be followed in order to get from A, which is your input, to B, which is the output (or result). Get a pen and paper, and start sketching out your ideas.
Plan your route before starting the journey!
Now, for experienced programmers, it is easy to jump straight in and start coding. The Khan academy tutorial has the task written out in plain English, with a tiny bit of pseudocode, so they've done all the thinking for you right? Wrong! It is still best practice to map out your own process. That way you can ask questions and get a complete understanding of the task at hand. But if you're ok with buggy code, go right ahead!
I'm going to show you how I did my planning, and then I will share my code at the end.
The Task
We have an array of prime numbers from 2 to 97.
Feed a random number into the binary search algorithm.
If the number is present in the array, the programme will return the index position of that number.
If the number is not present, the programme will return '-1'.
Binary Search
Binary Search is a really efficient way to find an item in an ordered list of data. In this case we have the list of prime numbers above. The search is a process of elimination. You narrow down the possible options by dividing the data in half over and over again, eliminating all the possible options until you are left with just one, which will be target.
Our minimum value is 2, which is at minimum index position 0.
Our maximum value is 97, which is at maximum index position 24.
Note: Because our array starts from index position 0, and ends at position 24, that means there are 25 values in the array.
How it works
To illustrate how this works, I am going to choose a random number and show how the algorithm will 'guess' my number.
Step 1
The programme starts by guessing the mid-point of our array, which is index position 12 in this case.
The algorithm establishes the mid-point in the following way:
My number = 67
Is my number equal to the first guess, i.e. is 67 = 41? No. My number is 67, is at position 18, and the first guess was 41, which is at position 12.
Step 2 & 3
We want the programme to compare the value of our number, 67, and the value held at index position 12, which is 41.
If 67 is greater than 41, we know we can eliminate all the values to the left of and including position 12 in the array, because they are all less than 41, which in turn is less than 67.
If the our number had been less than 41, we would do the opposite and eliminate the values to the right of and including position 12.
Step 4
Step 5
We now need to find our new mid-point, so we repeat Step 1 as follows:
We have arrived at our number!
This programme will keep running until it finds our number.
But what if we choose a number that is not present in the array?
We simply say to the programme, if the number we choose does not match any of the values in the array, it will give us an output to indicate that. In this case, I have asked the programme to return the value '-1'.
Edge Cases
Something I will touch on very briefly is Edge Cases. The programme that I have written above does not factor in what happens if I were to choose the values held at index position 0 or 24, which are the prime numbers 2 and 97. They are what is referred to as 'edge cases'. The values at the edges of an array.
So, I had to write a couple of extra lines of code to deal with them. I gave the programme specific instructions about what to do if I choose either number 2 or 97 as my random numbers. As with all programming, there are different ways to do everything. I will not go into detail, but here is my solution:
If my number is 2, return the value: index minimum;
but if my number is 97, return the value index maximum.
The Code
The Main Challenges
- Getting to grips with for loops and while loops required a lot of repetition. I completed the exercises on Codecademy and revisited them a few times to make sure that I fully understood the flow.
- The code performed really well when testing the mid points of the array, but some extra code was needed to test the edge cases.
- Although the code is neat and tidy, it could do with a bit of refactoring, so that's my task for another day!
Long story short, I finished it yesterday! Hooray!
It was a really fun process because it's like solving a puzzle. Who needs sudoku when you can code!
If you are thinking about coding, stop! Don't think about it anymore. Just get started!!! Codecademy is a great resource to start with, or you can check out these amazing tutorials from +Kingsley Ijomah He starts with html & css, moves on to Bootstrap, and then Ruby on Rails. The great thing about his tutorials is that he assumes that you have absolutely no prior knowledge of coding. The tutorials are for absolute beginners! Get started today!
About Me
I am not a programmer, I am a dabbler, with a curious interest in Mathematics. I have not worked commercially as a programmer, but I co-founded a software company back in 2008, and I have worked with programmers since then. The bulk of my experience is with html and css, but I have studied Ruby and a bit of Python, so I understand the key concepts and I can hold my own. I have recently made a foray into the world of MVC (Ruby on Rails), which is a whole new experience, but I did not have a project that I had coded from start to finish before, until now! So when I did my first git commit yesterday, it felt good!!!
So, I set myself a bit of a crazy challenge last week! https://t.co/LMg6zSwWI5 #Algorithms #JavaScript #Girls #Code pic.twitter.com/R9zMOB7anp
— Danielle Curio (@DanielleCurio) December 6, 2015
No comments:
Post a Comment