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.

Main content

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?

  • piceratops seed style avatar for user Vaibhav Bhattacharya
    Is this content meant for grade 10 students? or for college students?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • hopper happy style avatar for user CristianDelgado217
    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.
    (77 votes)
    Default Khan Academy avatar avatar for user
  • leaf orange style avatar for user GassanAly
    What are the prerequisite maths for learning algorithms?
    (24 votes)
    Default Khan Academy avatar avatar for user
    • leaf green style avatar for user Alexander Wu
      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).
      (2 votes)
  • leaf green style avatar for user Ann
    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!
    (2 votes)
    Default Khan Academy avatar avatar for user
  • aqualine seedling style avatar for user Kchakrabarty2500
    What is the difference between binary search and divide and conquer method ?
    (13 votes)
    Default Khan Academy avatar avatar for user
    • hopper cool style avatar for user Iron Programming
      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
      (2 votes)
  • blobby green style avatar for user amritha
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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
      (24 votes)
  • male robot johnny style avatar for user Lucian
    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.
    (2 votes)
    Default Khan Academy avatar avatar for user
    • spunky sam blue style avatar for user multi verse
      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.
      (2 votes)
  • leaf green style avatar for user it.codeperl
    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)
    Default Khan Academy avatar avatar for user
  • hopper cool style avatar for user Deadpool
    So then, a 600-number array should need, at most, 10 guesses?
    Edit: While using the above method.
    (2 votes)
    Default Khan Academy avatar avatar for user
    • piceratops seed style avatar for user vohrathegreat
      The logic behind a binary search is as follows:
      Where T is the total number of options and n is the number of times you've guessed,
      The number of options available for the next guess is (T/2^n) rounded upwards.

      Therefore, for T=600, after the 9th guess you will have (600/2^9) = 600/512 ~ 1.2 = 2 options left. So in 10th guess you have to find the answer.
      (9 votes)
  • blobby green style avatar for user kenson munthali
    i want to be a programmer but i don't know anything about it ..what could be a good start for me to be programmer?. i mean items of languages,which language should i learn first.?
    (6 votes)
    Default Khan Academy avatar avatar for user
    • leaf green style avatar for user cossine
      There is no particular language. Though it is useful to know multiple languages important to make sure you have good knowledge of computer science i.e. statistics, calculus, networking, embedded systems. Computer science is a big field so will have choose what you want to learn or focus on however you should learn foundational skills.

      But yeah starting programming is alright. If you want to become an electric/electronic engineer you generally focus on low-level languages.

      For data science Python, R are good languages.

      Try finding some textbook where you could Slader.com and consider taking some Udemy course or other online courses.
      (3 votes)