Skip to main content
Loading Explore guides…
Binary Search · Acedra
Home
Explore
Computer Science
Binary Search
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
45 segments
Copy
Hide video
0:00
Binary search is one of the most important algorithms in the world. It allows us to quickly find a number (some target value) in a sorted array of numbers or if there is a dictionary of words sorted lexicographically, we can quickly look up a word. Even though the idea of the algorithm is simple, you must be very careful while implementing it. The study from 1988 showed that only one in four textbooks has a correct implementation
0:30
of binary search (that might be much better now) but it shows that it's very easy to make a mistake. Even the Java library implementation had an incorrect implementation with overflow and it wasn't noticed for more than nine years. Let's say we were given a sorted array of size 7, values are indexed from 0 to n-1: from 0 to 6, and there is target value 10. We want to find the position of 10 in the array. The idea of binary search is simple.
1:05
Ask about the middle element, if it's equal to the target value return its position and terminate, otherwise go to the left or to the right. 6 is smaller than 10 and the array is sorted so 10 must be to the right. The remaining range in which we should search is from 4 to 6: between positions 4 and 6. Then repeat. Ask about the middle element (10), now it would turn out we hit the exact value and we return the index 5.
1:40
Possibly we could not find a value if it's not in the array and that happens if the remaining range becomes empty. If we ask about some value it turns out, let's say, greater than target value we go to the left but the range on the left is already empty then we terminate saying there is no such value. Usually, the problem tells us to then return -1 as the answer. Let's simulate the algorithm for the same array but target value 9.
2:12
We ask about the middle element, 9 is greater than 6, we go to the range to the right from 8 to 12. We ask about the middle element, it's greater than target then we need to look to the left, 8 is smaller than target, the target must be more to the right. But we are already out of range, we need to look somewhere there: to the left from 10 and to the right from 8 and when the range is empty we should return say -1 or some null.
2:47
At each step of the binary search algorithm, there is some remaining range in which we look for the target value. We usually represent that range with two variables Left and Right, that are the first and the last index in the range we need to somehow compute the middle element of the range. A lot of people use a formula M=(L+R)/2 that might be not integer then we take the floor. For interval of size 4, this would produce the first of two middle elements and that's perfectly fine.
3:25
The issue is (and that's the reason you should never use this formula) L+R might overflow, this value might be bigger than what type of L and R fits. For example in C++ and Java, int type fits values up to around 2 billion (2^31) and if you add two such values, the sum will overflow and you will have some mistake because of that, you will not compute the average correctly. There is another formula that always works and it is M = L+distance/2 = L+(R-L)/2.
4:08
If R and L are non-negative numbers that fit into some type then also their difference will fit in the type (assuming that R >= L which is true) then remember you should use the formula on the right. You can see here pseudocode for problem where we are looking for a target value in a sorted array a. The initial range is from 0 to n-1 if we index elements from 0 to n-1. And while the range is not empty (Left <= Right), we take middle element as
4:46
L + distance/2, this should be floor, in C++ and Java you just do that, In Python, you need double slash. If that element is already target you return the position mid, otherwise you want to know whether you should look on the right or on the left, you compare a[mid] with target. To write a correct condition for comparing a[mid] and target, I usually think about the sequence where I know now some middle element (a[mid] here =6) and I think what happens if target is 10?
5:27
If target is 10, then for sure I should look to the right no matter what exact values are here but I know the array is sorted. Then I do L=mid+1 which means that now L is here and R is still the same, otherwise I do the opposite, R=mid-1 which is the interval to the left. If the while loop finished and I didn't return at any moment the position of target value. It means I'm left with an empty range and I can return -1 or null which means there
6:04
is no target in the array. Sometimes there is no array and we still can apply binary search. Let's consider a problem where we are given X and we should check whether X is a square of an integer. Like 16 and 25, for them answer is yes and for 20 the answer is no. We are forbidden to use square root function in your language, that on real values computes the square root and then you can check whether that squared is X. You should do everything yourself. How to do it?
6:39
We can binary search the value of square root of X, start from range [0, X] and at each step of binary search ask about the middle value M and compare it with X, if M^2 is equal to X then say yes and terminate, otherwise check if M^2 is too big then you should look for smaller M and you go to interval to range from L to M-1, otherwise if M^2 is too small go to bigger values. The implementation will be very similar to the previous problem, it's just that we look at m^2 instead of a[m].
7:23
We talked about some examples but what about the time complexity of the binary search? Each step of the algorithm, we halve the size of the range (the remaining range) or we already finish. In the pessimistic case we'll keep doing that, from N we'll go to range N/2 (maybe floor which is even better for us), then N/4 and so on. The function that tells us what is the number of steps here is Log2(N) and that is the time complexity of the algorithm.
7:57
Usually, we just say that the time is logarithmic or it's log(n). Let's look at a harder problem now. Find the first value that is greater than or equal to X. We are given for example X=4, some array. Here we should return 5, the smallest value that is not smaller than X. Our previous approach would first check the middle element 6 and it should check whether this is a good element. Previously it was equal to target value now greater than or equal to X. The issue is we cannot just return 6.
8:37
This satisfies the condition but we look for the first such value (leftmost or smallest). Some hacky fix for that would be to also check the previous element and because the previous one is 5, that is also greater than or equal to X, 6 is not a correct answer. If the previous element was 3 then we would say that 6 is the answer. This is the first of those elements greater than or equal to 6. The drawback of this approach is that we must be careful about not going out of the array
9:17
(checking index -1) plus this might not work for some other problems. We are looking for something more general and that will be to store an extra variable ans like answer and when we meet a position or value that satisfies the condition we store it as a possible answer. Let's say answer will be that best value. After we see 6 is good but maybe there is something better smaller value that is greater than or equal to X then we need to look for that possibly better value in the left part.
9:52
Maybe there will be something smaller than 6. We ask about 3, 3 is not greater than or equal to X. Then we look to the right because maybe better answer will be there. We see 5, 5 satisfies the condition from the *statement and is better than 6 then we replace it as the best answer. We never terminate that while loop because we found the answer, we just keep looking for a better one. And after the while loop is finished we return the answer that is stored at variable ans.
10:30
Let's compare the implementation of lower bound problem with our initial implementation of binary search. Now it's extremely important that you understand this instead of just learning it by heart and having the same code each time. Sometimes you will need to modify the code. To do that efficiently you need to understand it and not just guess what happens. With green, I marked the main differences from the previous implementation.
10:58
First of all, we create a variable ans that is initially equal to some fake value that value will be returned if no element of the array satisfies the condition from the statement. If the condition was to find the first value >= X then maybe all values are smaller than X then what should we return? This is that fake value. We could possibly here put infinity or may be null if this is some pointer, whatever should be returned if there are no values satisfying the condition.
11:32
Then we have a check that the condition is satisfied if a[mid] >= target. In that case, we overwrite ans. This code would find the position of that first element. If you want the value then instead of mid you can have a[mid] here whichever you need to do. You could theoretically do ans = min(ans, mid) but we'll only keep getting better ans so it's not necessary. You can just leave it as it is because later you go to the left.
12:14
The reason for this is because if there is better answer it's on the left. There is no reason to look to the right then from this interval you get something much smaller R=mid-1. If you there find some value that is >= target, or in other words it satisfies the condition from the problem then you will override the ans to be a better answer. Otherwise, if the condition is not satisfied then look at that part where maybe there will be better values those that will satisfy the condition.
12:53
At the end when the range is empty, Left is not <= Right then return ans. Possibly that will be that fake value that is -1 or infinity. Sometimes the order of these two lines will be different. But you should understand if the condition is satisfied, so that happens then ans is that new position and you should think in which part left or right the better answer can be. For example, if you ask about 6 and that is greater than or equal to 4, but maybe there is something better more to the left.
13:36
The problem asks us for leftmost value or first value that is >= 4 Then we should try finding a better value here. On the other hand, so else is a case where we have, for example, 2 here and then looking to the left doesn't make sense because only smaller values are here. Then we go to the right which means which is L=mid+1. Rotated array is an example of a problem where it isn't enough to just look at the middle value to say whether we should go to the left or to the right.
14:12
Even more, it is an example of a problem where the input array isn't sorted and we should still apply binary search to get complexity O(log N). The problem is: somebody rotated a sorted array and your task is to find the smallest element in that new array after the rotation. It will be equivalent to also try to find that rotation at which position the new smallest element is. For example, somebody had an array [2 3 6 ...] and he rotated shifted 2 and 3 to the end.
14:52
What's the issue with looking at the middle element (15)? We cannot compare 15 with anything to say if we should go to the left or to the right. Previously, we talked about the possibility of comparing an element with the previous value or maybe the next one. But it isn't enough. If you have value 15 here, think about it this way, in some long array then its value isn't enough to say where is the minimum. Even its surrounding isn't enough 9 and 19.
15:27
Maybe there will be just like here, we had 2 on the right the minimum on the right or maybe we have minimum on the left 5, but then 90 80 50, here minimum is on the left. Value of 15 and its neighbors even neighbors of their neighbors it isn't enough to say where we should go. We should understand binary search better then to know what to look for in this problem. Let's get back for a moment to lower bound problem, where we were looking for the first value that is greater than or equal to 4.
16:06
Values that satisfy that condition are basically here. If we for each number say whether it satisfies the condition of being greater than or equal to 4. We can write [false false true true true true true]. Our task was to find the first true, in an array where the prefix was filled with falses and then there were trues. If it's this way, then we can apply binary search. We check the middle element if it's true it's a possible answer and we should look for the
16:45
more true to the left and the leftmost true to the left. If the middle value is false then for sure if there are any true, then it must be to the right. This is how you should think about binary search. It will be also possible to use binary search to find the greatest value not exceeding something. Then the fact where our number satisfies some condition is true for some prefix and then false. Possibly the whole array is true or the whole array is false.
17:19
For example in the lower bound if all numbers are smaller than X (the given minimum value) then there are only falses and we should return -1, we will never find a value that satisfies the condition. We should try to find the same property in our rotated array problem. The array should be partially false and partially true and we need to find the boundary between them. When we look at the sequence [6 7 ... 19 2 3] then what two parts we can see? The split is between 19 and 2.
17:59
One part is those big numbers that come from the suffix of the initial array (sorted array) and then there is 2 and 3. How can we distinguish between them? It isn't enough to compare middle element with something that was previously or later. It isn't enough to compare 15 with 9 and 19. What is important is to compare 15 with the first or the last element in the array. If I say that I compare a[mid] with a[0] and if it is greater than I say it is true, the condition is satisfied otherwise false.
18:40
Then I'm looking for the first false in the input and that's what binary search can do. Slight issue is that actually if I write sequence [2 3 7 9] the sequence that isn't rotated at all then the whole array will be true and it isn't correct to say that in that case, I'm looking for the first false. It's better to say that the condition is that, the number is greater than the last number, instead of greater equal than the first number.
19:21
Because in that case if I compare with the last number and if I check whether it's greater here I have an array of falses and it's correct to say I'm looking for the first false. The same was on the left, still if I compare with the last element it should be greater than that then true will be in some prefix. Then ask about the middle element if it's true what means greater than the last element then go to the right because you're looking for the first false.
19:55
If you have false then save that as a possible answer, we use a line ans is equal to this position (ans=m) and look to the left for maybe a better answer. Maybe false that is more to the left. You should think about binary search problems in terms of prefix of false and suffix of true or the other way around. Then you can find the boundary that is the last true or the first false. Ask about the middle element if it satisfies the condition you need, save it as a possible
20:31
answer and got to a half that is better, that can have even better answer. If it's false if it doesn't satisfy your condition that you need then go to that half that will have those trues. Try using the insight from the previous problem to now solve this one. There is an array that increases and then decreases if you draw those points values then it looks like a mountain and your goal is to find the maximum. Then what would be that false and true? What can you check?
21:09
Pause the video now for a moment and try solving this yourself. The array consists of two parts increasing and then decreasing and it's natural to split it at that position. We can say condition is: value is greater than the previous value and then we are looking for the last true in the array, that will be the maximum. You might think what happens with the first value do we treat the first value as being greater than the previous one? I would say that.
21:42
Yes, this is true either because we can treat the value just before that as minus infinity or we can just say if the situation is like that [5 3 1] then of course here we have false (whether value is greater than the previous one) false and the last true will be here 5 is fine. This should be the last of values that is greater than previous element that is not smaller than that, then it's a possible maximum unless the next value is even greater than that.
22:17
The condition that I would now use is a[m]>a[m-1], if value is greater than the previous value then it's true in that case. I do answer is m. This is a possible answer and maybe I will find a better one to the right. Maybe the last true is there, I do L=m+1 otherwise R=m-1. Is it possible that here I compare with a[-1]? It is, but I said I also want true for element a[0] that this is greater than that minus infinity, fake minus infinity to the left.
23:07
Then I would here add condition or m is 0, m is 0 or it is greater than the previous element, then I say I put true here and I'm looking for that last true in the array. Binary search can be also used for real values, for floats. Let's say we want to find square root of x with some precision. And again, we shouldn't use a built-in function. What can we do? Say we want to find square root of 2 up to some precision, let's say up to two places after a comma.
23:42
Then I start from range [0,2] and I binary search the middle element is 1. Is 1 smaller than or greater than square root, then I compare 1^2 against 2? I know that it's smaller so I need the square root of 2 must be bigger, the remaining range is [1,2]. The middle element is 1.5. Is 1.5^2 bigger or smaller than 2, it's bigger than 2, then the square root must be smaller than that. Then I check 1.25^2, this is smaller than 2 and the square root must be greater than that and so on.
24:30
We can repeat that and stop when we have enough precision. It means the distance between L and R is small enough that we can return the answer. Sometimes the problem will tell you allowed precision is up to 10^(-9), 0.000000001, then check whether R-L is still greater than that, if not then finish. See the implementation on the right again mid is the middle element, this time it's all on real values not on integers, there is no rounding.
25:09
At this position where at this place we compare mid^2 with target, we could also use <=, it's just that it almost never happens that two real values are equal to each other and it doesn't hurt us anyway. If we want to find square root of 4 and we'll ask about 2^2 compared with 4, the no matter if we say this is smaller or greater the remaining range will be for example, let's say [2, 4]. And we know that 2 is the real value if we compute that on integers but then we'll get
25:49
interval [2,3] to [2,2.5] and so on and eventually we will converge to [2,2+epsilon] anyway. What did we learn today? If you're looking for a target value in a sorted array - that's easier. You just check if the middle element is the target value, otherwise, go to the left or to the right. In harder problems, you're looking for the last or first element that satisfies some condition. A problem maybe doesn't necessarily state that. It will not tell you to find first value
26:24
that satisfies something. For example in that peak element problem, you are looking for the maximum value. It was your task to first think about how to split the input into two parts and then it was [true true true ...] for some prefix and then [... false] for some suffix, then you can binary search. And the last thing was binary search on real values that is also perfectly possible. Then you don't do L=m+1 then it is just L=m. You have some range you split in half and either right or left part.
27:02
You don't check if exactly the middle element is fine because it's hard to compare on real values. There might be precision errors. And that's it for this lecture. This is the first of, I hope, many. Please give me suggestions in the comments below if you want me to do something differently, if you have suggestions for the topics, ... All the codes and links to some problems you will find in the description or in the pinned comment. I hope you liked it and that you learned something today.
27:37
I'm Errichto and see you next time. Bye Bye.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat