Basic Searching
Linear Search/Simple Search
Let’s say that you woke up in the middle of the night and you really needed to talk to someone, but you are a sad, lonely, pathetic person, and you don’t have anyone to talk to. What would you do? I am asking for a friend.
Well, if it was me, I would go through the phone book, and just call people until someone agreed to talk to me. This is simple search or linear search. It is not terribly efficient, but in this case, there is not much of a better choice.
The phone book does not help me find a person to talk to, or my friend, whatever. Not the point. In Big O notation, this search method takes O(N) time. Which sometimes is not bad, but it is not always the best.
Binary Search
Let’s go back to the phone book example, and change it slightly.
Let’s say I was looking for any people named Marky Mark, because
I want to make fun of their names. Linear search would be a horrible
way to handle this. Because I would be searching through the As, then
Bs, etc.
A better solution is to go to the middle of the phone book,
if the value is higher than M, I would flip halfway towards the front,
then halfway from there, and so on.
In this way I am cutting the value
of the input size by half every time. So....
N/2 N/4 + N/8….etc.
For those of you who are not inclined to math, probably should
just quit everything you are doing and become a monk.
Just a suggestion.
That pattern is logarithmic. Which is cool and stuff,
because of math. Go look up logarithms, and learn about them.
Basics of Logarithms
What does Log N mean?
The important take away is that you are looking at something. And every time you are cutting the data you are looking at, and cutting it in half. This will continue until you reach your solution (either you found it or not). But, either way, you are never looking at more than half of the data.