[0:02]Yeah, our next topic is binary search. Binary search is a searching technique. It's one of the methods for search. There are two different methods, one is linear search and the second one is binary search. This binary search follows divide and conquer strategy. If you remember in divide and conquer strategy, we learn that if the size of a problem is large, break the problem into subproblems. Once the subproblem is, subproblems are solved, combine them to get the solution for main problem. So I have already taken some set of elements here. I have a list of elements that is 1 to 15, total 15 elements I have. Now let us learn how binary search works. First and foremost thing is to perform binary search, list must be in the sorted order. All the elements must be already in sorted order, then only you can perform binary search. This is a pre-requisite for binary search. So here I have the list of elements in the sorted order. Then let us see the approach of binary search. So for performing binary search, we need two index pointers. One is low, that is at a starting point, and the second one is high, that is at the ending point. Suppose I want to search for a key element 42, which is already present here. Let us see how binary search works. Low and high are taken. Low and high. Then we calculate mid. Mid is low plus high divided by 2, and we take floor value. What is low here? It is one. High is 15. This is 1 plus 15 by 2. This is 16 by 2, that is 8. This is mid. Now the value what I am searching is 42. Check at A of mid, is it 42? No. 42 is greater than this one, so definitely it's on the right hand side. How we can ensure that it's on the right hand side? Because the list is sorted order. So we ignore this part of a list and we search for this 42 in the second part of a list, second half of a list. So here we are dividing the list into two halves and we search in the second half. So we'll start from here until there. So we will bring low here, where mid plus one. So we'll change low to mid plus one. So mid is 8, so we'll bring low at 9, and high remains at 15 only. Now we search within this list. So for searching, again we calculate mid. 9 plus 15 by 2, this is 12. 9 plus 15, 24 divided by 2 is 12. So we met, we got it as 12, so it will check here, mid is 12. Is it the number that I am searching for, 47? No, this is 42. So my number is on the left hand side. So again, this sub list, we will split into two halves. Now my number is on the left hand side, so I'll search in this area. So I'll bring high here on mid minus one, that is 11. So high becomes 11, and this became, this is 9 only. So from 9 to 11, find out mid. 9 plus 11 by 2 is 20, so it is 20 by 2 is 10. So new mid will be, this is mid. Is it the number that I am searching for, 36? No, 30 is my number, 30 is smaller. So go on the left hand side. So change high to mid minus one. So high will also become 9. That is 10 minus one, 9. So both are 9, 9. So what is the mid value I got? Mid value is also 9, right? This is mid. Is it the number that you are searching for? No, the number is smaller, so it's on the left hand side. So when it's on the left hand side, we should check this side. So what should I change? High should be changed to mid minus one. So high becomes 8, and low is 9.
[4:44]So if you observe now, if you observe now, this 9 is greater than high. So low has become greater than high. But when we start, low will be on the left hand side, high is on the right hand side. So low cannot cross high. If it has crossed high means, we did not find the element. Element is not found. That's it. So if low becomes greater than high, the element is not found.
[5:23]Now, let us search key value 12. I'll take a key value as 12. I'm searching for 12. If I perform linear search, it can be found in just four comparisons. So let us see how binary search works. So first take low here and high at the ending index. So low and high, and also we know we have to find out mid, that is low plus high divided by 2, floor value. Low is 1, high is 15. Find out mid. This is 1 plus 15 by 2, that is 8. So 8 is mid. Is it the element that you are searching? It's 29. No, my number is 12. So 12 is smaller, so look into the first half of a list. So move high from here and bring it on mid minus one. So high becomes 7. High becomes 7, and low is still 1. So 1 plus 7 by 2, that is 8 by 2 is 4. Mid is 4. Is it the number that you are searching, 12? Yes, found. So search is successful at index 4. Here you can see, just in two comparison, I got a number. Right? So the number of comparison seems to be less than linear search. Now let us search for any element which is not present in the list and let us see what binary search does. I'm taking a key element 30. It's not present here. After 29 we have 31, so 30 is not present here. So let us trace this one. This is low, it is 1, and this is high, that is 15. Low and high, and mid. So low is 1, high is 15, and mid is 1 plus 15 by 2, that is 8. So we know well that it is low plus high divided by 2, and the floor value. 8. See, one thing, if you observe, I have solved already two keys. Every time I was getting mid as 8 only, because for this list from 1 to 15, mid is always 8. Okay. This is interesting. We'll see it further. Now, 8, the key is 30. Is it the key that you are searching for? No, my number is greater than 29, so look on the right hand side. So change low to 9. So low becomes mid plus one, that is 9, and this remains 15. So 9 plus 15 by 2 is 12. So now the new mid value is 12. This is mid. Again the mid of this list is 12, always, yes. So check here, is it the number 30? No, that's 47. So our number is smaller than that. So change high to mid minus one, that is 11. High will become 11, and low is 9. So this is 20 by 2, that is 10. So new mid will be at 10. This is mid. Is it the number, 36 is the number that you are searching? No, 30. 30 is smaller. So go on the left hand side. So what should change now? High should be changed to mid minus one. So high will also become 9, that is 10 minus one, 9. So both are 9, 9. So this is 9 plus 9 by 2 is 9 only. So what is the mid value I got? Mid value is also 9, right? This is mid. Is it the number that you are searching for? No, the number is smaller, so it's on the left hand side. So when it's on the left hand side, we should check this side. So what should I change? High should be changed to mid minus one. So high becomes 8, and low is 9.
[9:22]So if you observe now, if you observe now, this 9 is greater than high. So low has became greater than high. But when we start, low will be on the left hand side, high is on the right hand side. So low cannot cross high. If it has crossed high means, we did not find the element. Element is not found. That's it. So if low becomes greater than high, the element is not found. Now, let us write an algorithm for binary search.
[10:00]Binary search, it takes array of elements and the size, that is number of elements, and the key to be searched. These are the three parameters. And it returns the index of a element found. So instead of algorithm, I am writing it like a function. Then low will be at 1 and high will be at N. I'm not declaring them. L and H are the variables, integer variables. Now what it does? It will find out mid, that is low plus high divided by 2. It will find out mid. Then at mid, it will check, like we were doing here, mid we were getting it at 8. So at that place it will check if key that we are searching is equals to A of mid. If it is equal to A of mid. If so, then the element is found. Then what is the index of the element? That is mid. Return mid, element is found.
[11:27]If it is not that same element, then check if key element is less than A of mid. Means key element is on the left hand side.
[11:41]If it's on the left hand side, then what we should change? High should be changed to mid minus one. So H should be changed to mid minus one. If it is neither equal, nor less, then definitely it is greater. So then what we should change? Low to should change to mid plus one. Else low should change to mid plus one. Now this process will repeat, go on repeating until the element is found. So this has to be written in a loop. So I'll write in a loop. How long this loop should run? As long as low is less than or equal to high.
[12:46]If low became greater than high, it will stop and I should return not found. So I will return index zero. It means the element is not found. So this is the binary search algorithm, and this is a iterative process that is loop using loop. Okay. Let us, already we have taken this example, we have traced this. We have calculated mid and gone on the left hand side or the right hand side. All these things we have done. We have checked how it behaves in case of element is found and how it works if the element is not found. Now let us see the tracing of this one with the help of a tree. Let us do it. As per this example, first time when we are calling this algorithm, let us check how the mids are calculated. First time, mid will be 8. Yes, we have seen this. And if our element is smaller, then it will calculate mid from 1 to 7, that is 4, so this side it will be 4.
[14:11]And the right hand side if we check it from 5 to 7, then the mid value will be 6. And on the left hand side we'll have 1, and the right hand side we'll get 3, and the left hand side of this one is 7. Oh, so 5, and the right hand side of this one is 7. And the left of 12 is, see, if you check this one, leaving 8, 9 to 11, the middle is 10. And the left hand side of this is 9. Right hand side is 11. And on this side we will have 14. 13 on left hand side, 15 on right side. Now, let me show you quickly some examples. See if I am searching for 29. This algorithm will find out mid and go to 8, and that is 1 plus 15 by 2 is 8. Mid is 8, and element is found. So in 1 comparison, the element is found. If I am searching for an element 47, then it will first check at 8, and if the element is not 47, it is greater, so it will look on this side. That is 9 to 15, and the middle of that one is 47, so it will stop here, yes. Element is 47, mid of that is 12, so it will stop at 12. If the element that I am searching is 14, then first it will check at mid, this is 29, no. 8 is 29, my element is 55. Then it will go on the right hand side, mid, that is 12. So it is 47. No, element is 55, it's greater. So then mid of this one is 14, that is 55. Yes, element is found. So in three comparison, the element is found. Then maximum how many comparisons it is taking for searching any element? So that depends on the height of a tree. So at most how many comparisons are required? If I am searching for an element at index 7, that is 25, it will take four comparison. So maximum comparisons are dependent on the height of a tree, and the height of a tree is log n, that is 4, 1, 2, 3, 4. Right? So actually this is how many? See, there are eight elements here. Then 4, then 2, then 1. Or from here if I see, 1, then they are becoming 2, then they are becoming 4, then they are becoming 8. So how many times they are getting multiplied? How many times they are getting multiplied? That is four times. So that is 4. Levels are 4. So approximately, if I take these elements as 15 plus 1, that is 16 elements, then log 16 base 2 is 4. Right? Four comparisons required. So the time taken by binary search is log n. So from the tree we can analyze. And one more thing, if I am searching for any element, if I am searching for any element, which is not present, then what happens? Suppose I am searching for 65, then first it will go here, mid 8, then on 12, then on 14, then on 15, then it will try to go that side, but the element is not there.
[17:31]So it will stop on this side. Same way, if I am searching for any elements that are lying in between 55 and 62, it will stop on this side. Likewise, I can draw some external nodes to represents those elements which are not present in the list. And how much time it will take for unsuccessful search? 1, 2, 3, 4, stop. So again, maximum four comparisons are required. Now one more thing, if I am searching for any key, minimum how much time it may take? If I am searching for a key element present in the mid that is 29, then it will take only one comparison. So this is order of 1. Then maximum how many comparison it takes? It depends on the height of a tree, that is log n. So this is order of log n. So the minimum time of binary search is order of 1, maximum time is log n. So best case is, best case time is 1, worst case time is log n, average case time will also be log n, if you analyze this one.
[19:28]So best case is, best case time is 1, worst case time is log n, average case time will also be log n.
