If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

## Computer science

### Unit 1: Lesson 1

Intro to algorithms

# A guessing game

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)?
We'll return to binary search, and we'll see how you can use it to efficiently search for an item in a JavaScript array. But first, let's look at an algorithm for a trickier problem.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

## Want to join the conversation?

• Is this content meant for grade 10 students? or for college students? • 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. • What are the prerequisite maths for learning algorithms? • 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).
• 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! • What is the difference between binary search and divide and conquer method ? • 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
• 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? • 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
• 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. • 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.
• 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? • So then, a 600-number array should need, at most, 10 guesses?
Edit: While using the above method.  