Let's play a little game to give you an idea of how different algorithms for the same problem can have wildly different efficiencies. The computer is going to randomly select an integer from 1 to 15. You'll keep guessing numbers until you find the computer's number, and the computer will tell you each time if your guess was too high or too low:
Once you've found the number, reflect on what technique you used when deciding what number to guess next.
Maybe you guessed 1, then 2, then 3, then 4, and so on, until you guessed the right number. We call this approach linear search, because you guess all the numbers as if they were lined up in a row. It would work. But what is the highest number of guesses you could need? If the computer selects 15, you would need 15 guesses. Then again, you could be really lucky, which would be when the computer selects 1 and you get the number on your first guess. How about on average? If the computer is equally likely to select any number from 1 to 15, then on average you'll need 8 guesses.
But you could do something more efficient than just guessing 1, 2, 3, 4, …, right? Since the computer tells you whether a guess is too low, too high, or correct, you can start off by guessing 8. If the number that the computer selected is less than 8, then because you know that 8 is too high, you can eliminate all the numbers from 8 to 15 from further consideration. If the number selected by the computer is greater than 8, then you can eliminate 1 through 8. Either way, you can eliminate half the numbers. On your next guess, eliminate half of the remaining numbers. Keep going, always eliminating half of the remaining numbers.
We call this halving approach binary search, and no matter which number from 1 to 15 the computer has selected, you should be able to find the number in at most 4 guesses with this technique.
Here, try it for a number from 1 to 300. You should need no more than 9 guesses.
How many guesses did it take you to find the number this time? Why should you never need more than 9 guesses? (Can you think of a mathematical explanation)?
Want to join the conversation?
- So then, a 600-number array should need, at most, 10 guesses?
Edit: While using the above method.(794 votes)
- For binary search, the total iterations required to find a number would be atmost log2(total_array_size).
So for an array of size 600 (assuming the array to be sorted) the easiest way to find is,
calculate the total number of times 2 needs to be multiplied to get 600.
Multiplying 2, 9 times (2^9) gives 512.
But 2^9 < 600.
2^10 = 1024. 1024 > 600.
2^9 < 600 < 2^10.
if 2 is multiplied approximately 9.xx times 600 will be achieved. Since decimal counting is not appropriate in this scenario, rounding 9.xx to 10, that will be the maximum iterations required to find the desired number in a set of 600 sorted numbers.(1503 votes)
- Is this where the term "divide and conquer" comes from?(388 votes)
- There is some debate over whether binary search is a divide and conquer algorithm.
Usually, in divide and conquer you take a big problem and recursively divide it into smaller problems (that make up the larger problem when combined), until the sub-problems become small enough to be solved directly. Merge sort is the classic divide and conquer algorithm.
One can structure a binary search to behave in this manner. i..e searching for an element in the list can be broken down to the problems of searching for the element in the bottom half of the list and the top half of the list. Searching for an element in the bottom half of the list can be broken down into problems of searching for the element in the bottom half of the bottom half of the list and the top half of the bottom half of the list...
However, in binary search, each time we divide the problem into halves, one half is trivially solved (the element we are searching for does not fall within the range of elements in one of the halves). Instead of having to wait for this half to broken down into a small enough problem to solve (as in a classic divide an conquer strategy), we can immediately throw this half away. Some prefer the term "decrease and conquer" to divide and conquer for problems like this.
See https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/divide-and-conquer-algorithms for more info about divide and conquer problems.(316 votes)
- Is this content meant for grade 10 students? or for college students?(0 votes)
- The "size" of each leap isn't what determines the length of time it takes to find the correct number, only the size of the list (ergo, the number of leaps). An easy way to understand this is to look at what binary actually means: powers of 2.
So, in the first example from the reading it says that you should be able to find the correct number from a selection of 16 in 5 attempts. 2^4 = 16, but you can find the number in 4 clicks, but you still might need a 5th click to choose the number. In the second example, it says you should be able to find the correct number from a selection of 300 in 9 attempts. 2^8 = 256 so there's still the possibility you haven't found it, but 2^9 = 512 thus encompassing all 300 possibilities, so you will have found it by the 9th click. Please note that 2^8 = 256 and 300 - 256 = 44 does not mean you'll magically find the correct number out of 44 possible numbers. You'll only have one number left after the 8th click and will need the 9th to actually choose it
Therefore, with your example of 1000 elements, you just need to find the power of 2 necessary to encompass all 1000 elements. 2^10=1,024 so it will take 10 clicks maximum to choose the correct number.(79 votes)
- What are the prerequisite maths for learning algorithms?(24 votes)
- It really depends. Some basic algorithms don't require any math (other than, like, adding numbers).
To get really good with algorithms, you should have up to high school math. For example, asymptotics might involve the properties of logarithms. Calculus would also be helpful.
To be truly superb with algorithms, probability, linear algebra, discrete math, and multivariate calculus are all pretty good to have (like, on the level of machine learning).(60 votes)
- What happens if halving doesn't work and you need something different.What other techniques could I use.Though this process would rarely not work,I would like to know.(20 votes)
- there may be physical constraints that cause efficiency problems. for instance if your data is stored on a tape drive then a linear search will actually be faster. but using either method will find the answer.
if the list is stored on a device that takes longer to access some locations then it takes to access other locations or there are constraints on your ability to read any arbitrary location such as a tape drive where changing direction is very expensive then you need to take the time needed to access the data into account. your algorithm would have to be designed for the specific situation. for instance if you have a huge amount of data in a disk array you may be able to do multiple reads in parallel.(20 votes)
- This is going to be a horrible question or, at least, and embarrassing one, but, what are the areas of mathematics do I need to study to get through and even be good in CS and programming?? I am not particularly great at it the whole subject of math. Thanks in advance you all!(20 votes)
- if you have not taken the course on HTML yet on khan academy then suggest that you do because that course teaches you about the basics of programing and it is very easy to follow along (at least I think so)(4 votes)
- What is the difference between binary search and divide and conquer method ?(13 votes)
- A Divide & Conquer algorithm is an algorithm that uses recursion to create sub problems (dividing) which we solve (conquer) independently, and then group together to solve the main problem, like sorting an array.
A Binary Search is a searching algorithm that always splits the possible solutions by half.
One is a searching algorithm, and the other is a sorting algorithm.
Hope this helps,
- Convenient Colleague(15 votes)
- uhm...but if i do a linear search fro 1 to 9 wouldn't that trivialise the algorithm...I am still guessing and i didn't find the number after 9 guesses...so how does this work.could some one explain to me?(5 votes)
- You want to use the least amount of guesses possible.
Linear search for a target in a list of 300 numbers could take at most 300 guesses.
Binary search for a target in a list of 300 numbers could take at most 9 guesses.
9 guesses is less than 300 guesses, so the binary search is a better strategy(25 votes)
- 1. I want to revise mathematics for algorithm learning. How important it is? As I want to start from the very beginning of mathematics(those are needed to learn algorithms), i want to learn those like a game. Khan academy will be very helpful. But is there any alternative I should choose?
2. Which portions of mathematics I should focus and from where I should I start as a beginner?(15 votes)