Computer algorithms - Binary Search and Big O notation
There comes a time in every developer's life when he has to get acquainted with algorithms. Some who study Computer Science have it sooner, and some who study on their own have it later.
There is often a lot of chorus about algorithms. Not even so - they always arise when it comes to them. In one camp are those who believe that it is a purely academic discipline, which has nothing to do with real life.
In the other camp are those who believe that a developer who does not know the algorithms deprives himself of a very important and useful toolkit.
In my opinion, each side is right in its own way. Front-end developers really don't need algorithms if the work is not related to business logic. Building fronts in Vue/React/Angular, making them adaptive, beautiful and animated - you won't need such knowledge. The backend does all the hard work.
But when we need to write some business-logic, that uses non-trivial actions sequence, for example for forming the same list, (well, the backend team couldn't cram sorting for address book into sprint, do it on the client, you-so-not programmers) algorithms can be very helpful.
Let's take one basic algorithm, known as Binary Search, as an example.
We have an array of sorted numbers.
I guess a number that is in the array. And you have to guess it.
You must guess it with the fewest number of tries. After each attempt, I tell you whether the attempt was "too little" or "too much. Like "warm"/"cold."
The fastest and most straightforward solution to this problem in terms of code is "simple search" - start with the smallest number, and go all the way until you find the right one.
For example, I'm puzzling 416.
If you put a print inside the loop, you can count how many search operations there will be. I riddled the penultimate one, so they will be the number of numbers minus one.
There is another way - Binary Search.
It works like this: we start searching from the middle of the list.
Suppose we have a list from 0 to 1000, and we want to search for a number 600.
The number at the position of 500 is too much, or too little?
- Too little ?
Yep, so anything less than that does not interest us. We look in the remaining half.
- And at position 750 ?
- Too much.
With each try, we call the position of the number in the middle of the remaining list and discard the part where the mystery number does not fall. And repeat this until the number is found.
In this way it is not necessary to sift through the whole list one by one.
Declare the minimum search boundary - the first index in the list.
Declare maximal search boundary - the last index in the list.
Cycle until the lower bound is equal to the maximal one or the required index is found.If nothing is found, we return empty.
In the loop we start by looking for the index of the middle between the current minimum and maximum bounds. Having found it, take out from the array by this index the number - the candidate.
If the candidate is equal to the chosen number - that's great, we've found it.
If the candidate is greater than the mystery number, then we change the upper bound of the search - we decrease the current middle by 1.
If the candidate is less than the guessed number, then change the upper bound of the search - increase the current middle by 1.
If you add a print after let candidate = numbers[middle], you can see how the algorithm works.
Minimum = 0 Maximum = 15 Middle = 7 Candidate = 19 Target = 416
Minimum = 8 Maximum = 15 Middle = 11 Candidate = 110 Target = 416
Minimum = 12 Maximum = 15 Middle = 13 Candidate = 400 Target = 416
Minimum = 14 Maximum = 15 Middle = 14 Candidate = 416 Target = 416
The search found the needed number in 4 tries.
Let's imagine that we are searching for the index of a record in the address list, which contains 400,000 records.
How many search operations do we have to do when the number 301,067 is given, using a simple search ?
That's right, 301,067.
And using a binary search, 18.
Using a program that will work the first algorithm on the data above, you can go take the dog for a walk while the program does its magic.
There is something called Big O notation. It describes how fast the algorithm is to use. If we have a list of length n, a normal search will search it for an index at the rate of O(n) - the more items in the list, the greater the value of n. The binary search will search at O(log n). We always take the worst case, in this example, the number at the very end.
Just in case, let me remind you what a logarithm is
A logarithm is the power to which you must convert a number after log in order to get the number before the equal sign.
log(2)8 = 3
log(2)4 = 2
log(2)16 = 4
In addition to O(n) and O(log n), the most common complexities are
- O(1) is a constant. The complexity is always the same, for any amount of data. For example, comparing two numbers.
- O(n!) is a factorial. Example, the Salesman's Problem.
- O(n squared) - quadratic complexity. Example - bubble sorting.
Basically, the Big O notation is a benchmark to see how productive an algorithm is. With it you can estimate how long it will take to process certain data, depending on its size.
PS: Don't be offended by algorithms, sometimes they can be useful.
It might be interesting
Motorola ROKR E8 has been designed to offer a nice user experience for talk and music.