Binary search is a widely known and most implemented algorithm in different forms in Computer Science. It is a relatively essential algorithm to know because it's widely used, its popularity in interview questions and its performance.
A binary search algorithm: :
- Allows a user to search for a given value inside of a list.
- It runs in O(log n) time complexity - !Important.
- Can be written as a recursive function
Scenario
If you have a dictionary: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z and you want to find a single word in the dictionary, you would find it by doing binary search probably by not even realizing it.
Let's say you want to find the word House in the dictionary, you would open up the dictionary to the middle, and you'd notice that you are in the "M" section. You know that "House" is before the "M" section, so you would totally forget about the second half of the book.
So you've just cut through the input size, the number of elements into half remaining with A B C D E F G H I J K L. Again you would go into the middle of this section and notice that we are now in the F section. H is after F so you would ignore the first half and remain with G H I J K L. We again cut our input size into half and land on section I, we throw away everything after I because H is before I. We go to the middle of what is left G H I and we are now in the H section and we have successfully found the word House.
By this, you can find that it's efficient because we have only performed 4 operations in an input that has 26 elements. As our input size grows, the number of operations that we will perform will not grow proportionally but it'll grow logarithimically.
If we had an input size of about 4000 elements it will only take us about 12 operations to find the element that we are looking for.
We will be coding out our binary search in a recursive form. Recursion is an incredibly important concept to understand and be able to implement it in programming.
In the next post, I'll share out about recursion before we begin coding our binary search algorithm.
See you!
Top comments (0)