Main content
Implementing binary search of an array
Let's see how to think about binary search on a sorted array. Yes, JavaScript already provides methods for determining whether a given element is in an array and, if it is, its location (as do many programming languages), but we want to implement it ourselves, to understand how you can implement such methods. Here's a JavaScript array of the first 25 prime numbers, in order:
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];Suppose we want to know whether the number 67 is prime. If 67 is in the array, then it's prime.
We might also want to know how many primes are smaller than 67. If we find the position of the number 67 in the array, we can use that to figure out how many smaller primes exist.
The position of an element in an array is known as its index. Array indices start at 0 and count upwards. If an element is at index 0 then it is the first element in the array. If an element is at index 3, then it has 3 elements which come before it in the array.
Looking at the example below, we can read the array of prime numbers from left to right, one at a time, until we find the number 67 (in the pink box) and see that it is at array index 18. Looking through the numbers in order like this is a linear search.
Once we know that the prime number 67 is at index 18, we can identify that it is a prime. We can also quickly identify that there are 18 elements which come before 67 in the array, meaning that there are 18 prime numbers smaller than 67.
Did you see how many steps that took? A binary search might be more efficient. Because the array
primes contains 25 numbers, the indices into the array range from 0 to 24. Using the step-by-step instructions from the previous article, we start by letting min = 0 and max = 24. The first guess in the binary search would therefore be at index 12 (which is (0 + 24) / 2). Is primes[12] equal to 67? No, primes[12] is 41.Is the index we are looking for higher or lower than 12? Since the values in the array are in increasing order, and 41 < 67, the value 67 should be to the right of index 12. In other words, the index we are trying to guess should be greater than 12. We update the value of
min to 12 + 1, or 13, and we leave max unchanged at 24.What's the next index to guess? The average of 13 and 24 is 18.5, which we round down to 18, since an index into an array must be an integer. We find that
primes[18] is 67.The binary search algorithm stops at this point, since it has found the answer. It took only two guesses, instead of the 19 guesses that linear search would have taken. You can step through that again in the visualization below:
Pseudocode
We just described the binary search algorithm in English, stepping through one example. That's one way to do it, but a human language explanation can vary in quality. It can be too short or too long, and most importantly, it's not always as precise as it should be. We could jump to showing you binary search in a programming language like JavaScript or Python, but programs contain lots of details - due to requirements imposed by the programming language, or because programs have to handle errors caused by bad data, user error, or system faults - and those can make it hard to understand the underlying algorithm from studying just the code. That's why we prefer to describe algorithms in something called pseudocode, which mixes English with features that you see in programming languages.
Here's the pseudocode for binary search, modified for searching in an array. The inputs are the array, which we call
array; the number n of elements in array; and target, the number being searched for. The output is the index in array of target:- Let
min = 0andmax = n-1. - Compute
guessas the average ofmaxandmin, rounded down (so that it is an integer). - If
array[guess]equalstarget, then stop. You found it! Returnguess. - If the guess was too low, that is,
array[guess] < target, then setmin = guess + 1. - Otherwise, the guess was too high. Set
max = guess - 1. - Go back to step 2.
Implementing pseudocode
We'll alternate between English, pseudocode, and JavaScript in these tutorials, depending on the situation. As a programmer, you should learn to understand pseudocode and be able to turn it into your language of choice - so even though we're using JavaScript here, it should be straightforward for you to implement pseudocode using other languages.
How would we turn that pseudocode into a JavaScript program? We should create a function, because we're writing code that accepts an input and returns an output, and we want that code to be reusable for different inputs. The parameters to the function—let's call it
binarySearch— will be the array and target value, and the return value of the function will be the index of the location where the target value was found.Now let's go into the body of the function, and decide how to implement that. Step 6 says to go back to step 2. That sounds like a loop. Should it be a for-loop or a while-loop? If you really wanted to use a for-loop, you could, but the indices guessed by binary search don't go in the sequential order that a for-loop makes convenient. First we might guess the index 12, and then 18, based on some computations. So a while-loop is the better choice.
There's also an important step missing in that pseudocode that didn't matter for the guessing game, but does matter for the binary search of an array. What should happen if the number you are looking for is not in the array? Let's start by figuring out what index the
binarySearch function should return in this case. It should be a number that cannot be a legal index into the array. We'll use -1, since that cannot be a legal index into any array. (Actually, any negative number would do.)The target number isn't in the array if there are no possible guesses left. In our example, suppose that we're searching for the target number 10 in the
primes array. If it were there, 10 would be between the values 7 and 11, which are at indices 3 and 4. If you trace out the index values for min and max as the binarySearch function executes, you would find that they eventually get to the point where min equals 3 and max equals 4. The guess is then index 3 (since (3 + 4) / 2 equals 3.5, and we round down), and primes[3] is less than 10, so that min becomes 4. With both min and max equaling 4, the guess must be index 4, and primes[4] is greater than 10. Now max becomes 3. What does it mean for min to equal 4 and max to equal 3? It means that the only possible guesses are at least 4 and at most 3. There are no such numbers! At this point, we can conclude that the target number, 10, is not in the primes array, and the binarySearch function would return -1. In general, once max becomes strictly less than min, we know that the target number is not in the sorted array. Here is modified pseudocode for binary search that handles the case in which the target number is not present:- Let
min = 0andmax = n-1. - If
max < min, then stop:targetis not present inarray. Return-1. - Compute
guessas the average ofmaxandmin, rounded down (so that it is an integer). - If
array[guess]equalstarget, then stop. You found it! Returnguess. - If the guess was too low, that is,
array[guess] < target, then setmin = guess + 1. - Otherwise, the guess was too high. Set
max = guess - 1. - Go back to step 2.
Now that we've thought through the pseudocode together, you're going to try implementing binary search yourself. It's fine to look back at the pseudocode - in fact, it's a good thing, because then you'll have a better grasp of what it means to convert pseudocode into a program.
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?
I passed all of the steps, but number of guesses shows 0. Why is this?
[Edited to show only code necessary for question ]
Code used to increment counter for number of guesses:gcnt = gcnt++;(19 votes)
"Let min = 0 and max = n-1."
Why do you set max to n-1? Why not n?(16 votes)
If max was set to n it would point to a location outside of the array. In this instance a zero indexed array is being used, meaning numbering starts at zero instead of 1 (which would be a one indexed array and also what most people are used to) and has values at indexes 0 to n-1.(44 votes)
I am on the final step, and I actually passed it, but I don't understand the Program.assertEqual(doSearch(primes, 34) 20); part. I wrote the same thing underneath with only changing the numbers, but I get a message that says "assertion error: 14 is not equal to n" where n is the number that I chose as the final parameter in that Program.assert....(doSearch...) command.
How do I figure out that it wanted 20, then 14, then 15 without it having to tell me?(14 votes)
I had the same problem : from what I understood the assertEqual function will just see if the number returned by your function, which is put as the first parameter in Program.assertEqual here, [doSearch(primes,73)] and the second parameter [20] are the same. It will return an error if they aren't in this exercise ! So just count in the array where your prime number is indexed, and put that as your second parameter. :) If it's not a prime, the second parameter should be -1.(16 votes)
Please, help me. I can't understand what's wrong with that.
var doSearch = function(array, targetValue) {
var min = 0;
var max = array.length - 1;
var guess;
while (max > min) {
guess = floor((max + min)/2);
if(array[guess] === targetValue) {
return guess;
}
else if(array[guess] < targetValue){
min = guess + 1;
}
else {
max = guess - 1;
}
}
return -1;
};
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
var result = doSearch(primes, 73);
println("Found prime at index " + result);(6 votes)
You must set the while loop check condition towhile(max >= min)(7 votes)
I'm stuck on the 3rd step. I was able to print the total number of guesses, but it does not let me go to the next step, and the print is just appearing when I use the ProgramAssertEqual otherwise it does not appear. I also would like to make it appear without this last command.
Code:
[Edited to only show relevant code]var doSearch = function(array, targetValue) {
...
var guessTotal = ...;
while(...) {
...
if(max === min) {
println("Number of guesses " + guessTotal);
}
}
};(8 votes)
Hello!
I've been trying for days to get past step one in the binary search challenge, but I keep having the error message "Hm, do all of you assertions pass?" and I can't figure out what is wrong with my code... I've tried to start over and rewrite my code but impossible to find what's wrong...(8 votes)- "Hm, do all of you assertions pass?" basically means that your code is giving you a different result than the one expected by the Program.assertEqual statement
The code you have shown looks okay (I am assuming that your are hiding the conditions you are using by writing "..." and that is not the code you literally wrote). The conditions on your while loop or if statements are probably the culprit.(5 votes)
- In these examples any value with x.5 is rounding down. I thought the tenths being from 5-9 would round upwards. Please explain.(5 votes)
- it might be late but the program above specifically rounds the numbers to the smaller value (to not skip an array value during rounding a number up)which is done in program using
println( floor(random(0,1)) );
/* prints 0 mostly
(by rounding to the lowest integer value) */
Note that you can round to the higher integer number by using ceil(); and also in the normal ( lower value when less than 5 in tenth decimal and higher otherwise ) way by using round();(1 vote)
Hi everyone I have a question. This lesson here "Implementing binary search of an array" assumes all numbers are listed in order, but it does not tell me how do I think about it if the numbers are mixed. Does that means all numbers first need to be sorted before I do the binary search or it can be done in an unsorted array as well?(3 votes)- Binary search only works on sorted lists. It needs to be sorted, in order for us to correctly eliminate half the choices at each step. If our guess gives us a value > than our desired value, then we know the choices to the right of it can not contain our value, because the values are sorted. If the values were not sorted we would not know whether our desired value was within the choices to the right, and as such we could not eliminate those choices.
If the numbers are not sorted then you can do a linear search, which looks at every value one by one. The worst case running time for this is O(n)
However, if you will need to perform a search on the list several times it may be worth while to sort the list, then use binary search on the list for each search. A typical sorting algorithm like merge sort will have a worst case running time of O(n log n) and each binary search will be O(log n).
If we assume we needed to search the array n times the total worst case run time of the linear searches would be O(n^2)) . On the other hand, sorting once, O(n log n), with n binary searches, O(n log n), would have a total worst case run time of O(n log n) . So we can see, that as the number of searches we want to perform on the array starts to approach n, sorting first becomes a decent option.
Another possible option for repeated searches, is constructing a hash table, O(n), which has average run time of O(1) for searches.
Hope this makes sense(6 votes)
How exactly do you translate pseudocode into JavaScript, and vise versa?(3 votes)- The pseudocode tells you what basics steps you need to implement the algorithm.
Pseudocode to JavaScript process:
1) Copy paste the pseudocode into a comment in your code to act as a road map for your code.
2) Under each step of the pseudocode comment, convert it into a JavaScript instruction that implements that step.
e.g. "Let min = 0" in pseudocode becomesvar min = 0;in JavaScript
JavaScript to Pseudocode process:
1) Convert each line of your JavaScript code into pseudocode. The pseudocode should be a basic description of what the code is doing. Ideally, it should be possible to follow it by hand without a computer, and it shouldn't rely on any syntax specific to any programming language.
e.g.if(x<y){ return -1; }-> "If x is less than y, then return -1"(5 votes)
prime number is not a normal number? what is a prime number? what is the pattern used here?
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
thanks(2 votes)- A prime number is a positive integer that has exactly two factors, itself and 1. For example, 13 is only divisible by 1 and 13, so it is prime. However, 6 is divisible by 1, 2, 3, and 6, so it is not prime (i.e. it is composite).(5 votes)
