Algorithms are an integral part of computer science, and in fact our day to day lives. We use algorithms all the time without thinking about it, in a way our brains are wired to figure out solutions to problems. As computer programmers and application developers we need to know how to translate these solutions into code and ideally effective and efficient code.
In this tutorial series I am going to break a bit from my normal C# Google tutorials. Over the last several months I have seen a lot of people talk about algorithm performance and big O. This is something I learned a very long time ago in collage. After more then 20 years a lot of this has become instinct to me rather then something I was doing with direct intent. When designing an algorithm it is best to know exactly what you are doing and why you are doing it. As someone who has been an application developer for more then twenty years somethings become more instinctive and less purposeful. I have always enjoyed writing tutorials so I thought that I would write a tutorial series on this, in order to get it strait in my own head. I intend to put my normal spin on the series. This will be as simple as possible and the examples will just work.
[wp_ad_camp_3]
Algorithm series
- A gentle introduction to algorithms and bigO
- Algorithms Constant Time O(1)
- Algorithms Linear time O(n)
- Algorithms Logarithmic Time O(log n)
- Algorithms Quadratic time O(n2)
What is Logarithmic Time?
Logarithmic time implies that an algorithms run time is proportional to the logarithm of the input size. In Big O notation this is usually represented as O(log n).
What is a logarithm?
For those of us who have not been in School in a while.
In mathematics, the logarithm is the inverse operation to exponentiation. That means the logarithm of a number is the exponent to which another fixed number, the base, must be raised to produce that number. In simple cases the logarithm counts factors in multiplication.
If that explanation wasn’t much help to you either I recommend you go and watch this video. Its been a very long time since I was in school after searching high and low. I ended up watching a video about it on khan academy I recommend you watch it.
Binary Search
I actually learned binary search after bubble sort. I found it just smart. Lets go back to our book example from the first article. You have a book in front of you, I want you to find page 62. How would you proceed? You could use a linear option and just start at page one and work your way until you hit page 62. Worst case if there was 62 pages in your book you would have to flip though 62 pages to find the correct page. What if I told you there was a better way. A faster way?
This is a binary search. With a binary search we find the middle point of the data and check if the number we are looking for is higher or lower. So if we have 100 pages and we are looking for page 20. Then the middle would be 50.
- 1.We then check if 20 is higher or lower then 50.
- 2. Its lower so we split 50 in half and get 25.
- 3. We then check if 20 is higher or lower then 25.
- 4. Its lower so we split 25 in half and get 13
- 5. We then check if 20 is higher or lower then 13.
- 6 Its higher so we split (25 + 13) in half and 19.
- 7. We check if 20 is higher or lower than 19.
- 8. its higher so we split (25 + 19) in half and get 22.
- 9. We check if 20 is higher or lower than 22.
- 10. Its lower so we split (19+22) in half and get 20.
- 11. We check and find that 20 is the correct number.
So if we had used the linear solution we would have had to check 20 pages in order to find the correct page. However with binary search we only had to do 11 checks. With each check we are making we are throwing away half of the data. This makes Logarithmic Time algorithms very efficient for large sorted lists of data.
[wp_ad_camp_5]
Conclusion
Binary search is a logarithmic algorithm. Doubling the data only means that you need to preform one extra split. This can be very effecting for searching large sorted lists.