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

Binary search

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one. We used binary search in the guessing game in the introductory tutorial.
One of the most common ways to use binary search is to find an item in an array. For example, the Tycho-2 star catalog contains information about the brightest 2,539,913 stars in our galaxy. Suppose that you want to search the catalog for a particular star, based on the star's name. If the program examined every star in the star catalog in order starting with the first, an algorithm called linear search, the computer might have to examine all 2,539,913 stars to find the star you were looking for, in the worst case. If the catalog were sorted alphabetically by star names, binary search would not have to examine more than 22 stars, even in the worst case.
The next few articles discuss how to describe the algorithm carefully, how to implement the algorithm in JavaScript, and how to analyze efficiency.

Describing binary search

When describing an algorithm to a fellow human being, an incomplete description is often good enough. Some details may be left out of a recipe for a cake; the recipe assumes that you know how to open the refrigerator to get the eggs out and that you know how to crack the eggs. People might intuitively know how to fill in the missing details, but computer programs do not. That's why we need to describe computer algorithms completely.
In order to implement an algorithm in a programming language, you will need to understand an algorithm down to the details. What are the inputs to the problem? The outputs? What variables should be created, and what initial values should they have? What intermediate steps should be taken to compute other values and to ultimately compute the output? Do these steps repeat instructions that can be written in simplified form using a loop?
Let's look at how to describe binary search carefully. The main idea of binary search is to keep track of the current range of reasonable guesses. Let's say that I'm thinking of a number between one and 100, just like the guessing game. If you've already guessed 25 and I told you my number was higher, and you've already guessed 81 and I told you my number was lower, then the numbers in the range from 26 to 80 are the only reasonable guesses. Here, the red section of the number line contains the reasonable guesses, and the black section shows the guesses that we've ruled out:
In each turn, you choose a guess that divides the set of reasonable guesses into two ranges of roughly the same size. If your guess is not correct, then I tell you whether it's too high or too low, and you can eliminate about half of the reasonable guesses. For example, if the current range of reasonable guesses is 26 to 80, you would guess the halfway point, (26+80)/2, or 53. If I then tell you that 53 is too high, you can eliminate all numbers from 53 to 80, leaving 26 to 52 as the new range of reasonable guesses, halving the size of the range.
For the guessing game, we can keep track of the set of reasonable guesses using a few variables. Let the variable min be the current minimum reasonable guess for this round, and let the variable max be the current maximum reasonable guess. The input to the problem is the number n, the highest possible number that your opponent is thinking of. We assume that the lowest possible number is one, but it would be easy to modify the algorithm to take the lowest possible number as a second input.
Here's a step-by-step description of using binary search to play the guessing game:
  1. Let min=1 and max=n.
  2. Guess the average of max and min, rounded down so that it is an integer.
  3. If you guessed the number, stop. You found it!
  4. If the guess was too low, set min to be one larger than the guess.
  5. If the guess was too high, set max to be one smaller than the guess.
  6. Go back to step two.
We could make that description even more precise by clearly describing the inputs and the outputs for the algorithm and by clarifying what we mean by instructions like "guess a number" and "stop." But this is enough detail for now.
Next up, we'll see how we can use binary search on an array, and discuss how to turn descriptions of algorithms into actual working code.

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?

  • leaf green style avatar for user pawel.englert
    Why do we need round down the average? Could we round up instead?
    (32 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Short Answer

      Rounding up works too.

      Long Answer

      What is important is the number of elements to either side of the guess.

      If the number of elements remaining are odd then we will have (n-1)/2 element above and below our guess. No rounding is required.
      If the number of elements remaining are even then we will have n/2 elements on one side of the guess and n/2-1 elements on the other side, regardless of whether we round up or down.
      (the rounding determines whether the smaller chunk will be above or below the guess)
      After we look at the value of our guess we will be able to eliminate the elements above or below our guess.

      The number of guesses required to find a particular element will be different depending on whether we round up or round down.
      However, if we performed a series of binary searches to find every element, one by one,and took the grand total of the number of guesses from all of these searches, the grand total would be the same regardless of whether we round up or down. This means that the average number of guesses to find an element is the same, regardless of whether we round up or round down.

      Hope this makes sense
      (79 votes)
  • leaf red style avatar for user Jeanne Gottschalk
    This statement at the end of the second paragraph is not at all obvious to me. ("If the catalog were sorted alphabetically by star names, binary search would not have to examine more than 22 stars, even in the worst case.") Why is that so?
    (19 votes)
    Default Khan Academy avatar avatar for user
  • ohnoes default style avatar for user KL
    Khan Academy Algorithm in 10 easy steps
    1. open your device
    2. open your browser
    3. type "Khanacademy.org" on your browser
    4. select your preferred courses
    5. watch the videos if they're any
    6. read any articles if they're any
    7. answer all of the practices
    8. complete all the challenges and tests
    9. click the X on the khan academy browser
    10. turn off your computor
    (18 votes)
    Default Khan Academy avatar avatar for user
  • male robot hal style avatar for user Krish
    I don't quite understand the binary search steps. Could someone please explain it to me?
    (6 votes)
    Default Khan Academy avatar avatar for user
  • starky sapling style avatar for user Alan Savage
    so is this binary search how programs like the akinator work? obviously more complicated but the same asks the average out of a pool of data, eliminate then continue?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      The algorithm for akinator is secret, but it is likely similar to binary search in the sense that with each question it tries to eliminate roughly half of the choices.

      Likely it has a bunch of attributes for each character where each attribute is either True or False.
      It probably picks question where the split between True and False for the answer to the question, for the remaining characters, is as close to 50/50 as possible. That way each question will roughly eliminate close to half of the characters.
      (16 votes)
  • starky tree style avatar for user David
    How does the computer determine whether the correct answer is higher or lower than the guess? If it already knows what the correct answer is, then guessing is redundant.
    (4 votes)
    Default Khan Academy avatar avatar for user
  • area 52 blue style avatar for user huseynov.rza.00
    #include <bits/stdc++.h>

    using namespace std;

    int main() {
    int n; // the range of numbers
    int x; // the number which we are looking for
    cin >> n >> x; // input
    if (x == n || x == 1) {
    cout << int(log2(n)) + 1 << endl; // we have to check this because there are some float precision problems while dividing (minn + maxx) to 2
    return 0;
    }
    int minn = 1, maxx = n; // the ranges which guesses are reasonable
    int cnt = 0; // the number of searches
    while (minn < maxx) {
    cnt ++; // we have to increase the number of searches in each search
    int midd = (minn + maxx) / 2; // the middle of our range
    cout << cnt << " " << minn << " " << midd << " " << maxx << endl; // to observe the changings
    if (midd < x) {
    minn = midd; // our midd must be higher to reach x, that is why we should increase midd
    }
    else if (midd > x) {
    maxx = midd; // our midd must be lower to reach x, that is why we should decrease midd
    }
    else {
    cout << cnt << endl;
    return 0; // end program
    }
    }
    }

    this is a good c++ sample code to observe binary search written by me.If there is any problem you can tell me
    (5 votes)
    Default Khan Academy avatar avatar for user
  • aqualine ultimate style avatar for user Gyan
    I don't understand the binary search steps, not at all,

    1.Let min = 1min=1m, i, n, equals, 1 and max = nmax=nm, a, x, equals, n.
    2.Guess the average of maxmaxm, a, x and minminm, i, n, rounded down so that it is an integer.
    3.If you guessed the number, stop. You found it!
    4.If the guess was too low, set minminm, i, n to be one larger than the guess.
    5.If the guess was too high, set maxmaxm, a, x to be one smaller than the guess.
    6.Go back to step two.

    can someone please explain this to me briefly
    (4 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      1) The target is somewhere between the smallest and the largest possible number.
      2) So, guess the number in the middle between the smallest and the largest.
      3) If you found the target you're done
      4) If your guess was too low, then the target must be bigger than your guess. So the lowest possible number for the target is your guess + 1
      5) If your guess was too high, then the target must be smaller than your guess. So the largest possible number for the target is your guess - 1
      6) Go to step 2

      The idea is we eliminate half of the possible numbers with each guess. So, it doesn't take many guesses before there is only one possible number left.

      Hope this makes sense
      (11 votes)
  • duskpin ultimate style avatar for user Zachary Koball
    to start algorithms should you have a complete understanding of programing.
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Here's a test to see if you're ready to do the algorithms section here:
      Can you write a program that finds the sum of the odd valued elements in an array ?
      e.g.
      oddSum( [2, 3, 4, 6, -2, 0, 1, 5] ) = 9
      Explanation: The odd elements are 3, 1, and 5, which have a sum of 3+1+5= 9

      If you struggle with that task, you should probably brush up on your programming skills before attempting this course.
      (11 votes)
  • hopper jumping style avatar for user lianamleeee
    How do you do it in code?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user jboyle
      In order to write binary search in code, you must have an array that is in order. Have a min variable set to 0 and a max variable set to the length of this array. Now find the middle of these two values, and then check to see if the value in the middle is higher, lower, or equal to the number you are searching for. If it is lower, set the max equal to the middle index, and if it is higher, set the min equal to the middle index. Repeat this process until the middle index is equal to the value you are looking for.
      (11 votes)