Binary Search Introduction | Theory + Code | Order Agnostic Binary Search

Hey everyone, I hope you all are safe and doing good. So in the previous lecture we have seen linear search algorithm. There is one more searching algorithm that is better than the linear search. And that is binary search algorithm. So this thing we'll see in this video. What is binary search algorithm? Why we call it binary search? And how this is better than linear search? Uh the obviously the core concept like the working of binary search algorithm and uh you can see the time complexity of this algorithm. And we will also see improved version of this, that is order agnostic binary search. Okay, so all these things we'll discuss in this lecture. First, what is binary search algorithm? See, in linear search if there is an array given and you have to search an element from the given array, we simply do we compare that target element with all the element sequentially, linearly. We start from the first element and start searching. Like we have something like this. So if you want to find out minus one, if you have to find out minus one, I mean you have to search if minus one exists in this array or not, then in linear search we start comparing. Is this minus one? Is this minus one? Minus one? Minus one? Yes, this is. So we return the index, something like this. And obviously in the worst case, the element is at the last or maybe the element is not present. So you have to compare with all the uh numbers, whatever the array size is, and the complexity is we know in big O notation order of n. Right? Now, binary search it's is better than this. But very first, let me just tell you one thing, the prerequisite to perform this binary search algorithm is this array must be sorted in ascending order. Either it's ascending or descending order. But by default we assume that array is in ascending order. Okay? To perform binary search. So if array is something like this, it's not sorted array, we cannot apply binary search. First you have to sort this array. So array is something like this to perform binary search. Something like this. So this array is we know sorted in ascending order. Yeah, you can apply on this array binary search. Okay? Now, how binary search works? Basically, we'll not start searching from the first element. We know this is the start or the low or this is high. There are two pointers or two like variables we have. This is like two pointer approach. So either you can have the start or this is end or this is I or this is J or this is low or this is high. It's up to you. Right? Now, first calculate the mid, mid of this array. How to calculate mid? The index is see, we have 0 1 2 3 4 5. Index is this. So low plus high low plus high divided by two, that would be mid. So 0 plus 5 divided by two in integer we are taking int, not double because int index is definitely int. So mid would be 5 divided by two, so that is two. It's 2.5 but we take int so it's two. Now mid is here. This is mid. So you need like basically three variables. Right? So we have divided basically in almost this array in the half, almost half. Now, if the key you want to find out key is equal to 11. Suppose target element is 11, you want to search 11 is there or not. Because it's searching algorithm, right? Now we know just compare this key with the middle element. You know this mid now, mid is two. So we know we have the middle index. So we can directly access whatever is element at the middle, at mid. So like this, a r r of if the name of this array is this, so a r r of mid will give you eight. So you compare the target element with this mid element. If it is equal to the target element or the key element, simply return mid. That's it. If it is 11, so return mid and mid is right now two. So yeah, we got our value back. If this is not equal to the mid element and if the key element is greater than the mid element, greater than the mid element. Now, it's 11 is greater than eight. Okay? Now say that definitely this uh target element lie in this half. Yes? Because we know array is sorted. If this is eight and our target element is 11, that is more than eight. So we can we can definitely say that we cannot find 11 in this half. That would be definitely in right half. So we have reduced our search space by half directly. Even I mean after only one comparison because we have compared with this. So after one comparison we have directly divided our search space into half. So you have to search in this half only right now. So now if you have to search in this half, now this is our search space right now. Okay? Now we know obviously you search from here to here, we know the same approach you have to follow. Now again find out mid of this and again the same approach. So now this high, this pointer is here only. But now this low or the start of this array is here. Because you have to search from this to this. We have eliminated eliminated this part. So now you have to modify your low. So it's very simple. We can simply do low is equal to what? This mid plus one. Mid plus one. Now right now here we have low. And here we have our high. Simple. I mean not height, it's high. So just apply the same approach again, find out the mid. Right? Again compare with the mid, the target is 11 or not. I mean the target is the same element or not. Now so again compare. You have to search it in the right half or the left half because array is sorted. Right? So this is basically binary search. Now why this is known as binary search? I guess from this procedure you easily uh can find out. Because binary means two, we know. Right? And repeatedly we are dividing this array into two halves. So that's why it is known as binary search. That's the reason. Okay? Now, see binary search basically it finds a target value and it does this within a sorted array. The condition is the array should be sorted. It repeatedly divides the search space in half. Okay, so it it is a searching algorithm. Now why it's binary? Because uh as the name suggests, it divides the array in two halves. So that's why it's binary. Binary means two. Until the the same process we repeat until we find the element or search space is exhausted. Now what does that mean? I'll show you practically, don't worry. Okay? So if you want to find out I mean you would to write down the algorithm, then simply first we do is first step is what? You have to find out the middle element in the array. Second step is compare the middle element with the target element. Now within that you can write down if the target element is equal to the middle element, return mid. If the target element is greater than the middle element, then search in the right half. If target element is less than middle element, search in the left half. Simple. And you have to repeat these steps until you find your until the target element you find in that array or the search space is exhausted. These are simple four five steps. Okay? Let me show you this thing. With let's take one example, I'll show you this thing. Right? Then we'll analyze the complexity as well. So we have this array. Suppose. So here we have our low. And here we have our high. You can take start or end or I or J, whatever variable name you want to take, you can take. Right? And the key, suppose the first case is the first case is you have to find out suppose key is five. You have to find out this five exist or not. Array sorted, we can easily apply here binary search. We'll not go for linear search. If array is sorted because that would be I I'll show you the time complexity as well. And we know the time complexity basically is how many basically the number of comparisons. Okay? I'll show you. Key is five. Now in this case, I can say can I say like low high? Low is zero and high is we know it's nothing but the index. It's zero and it's eight. So first step is find out the mid. So 0 plus 8 divided by two, that would be four. So now mid is here. Our mid is here. Compare this. Is this equal to the key? Key you want to find out five. Five and 15, no. This is not equal. This five is less than the middle element. Means we will search less than means it will definitely in this half only. That's it. You don't have to search in that half. Right? So obviously if low is still zero but high now you have to modify. Now high should be here. Because you have to search from here to here. That's it. Because we have eliminated that part. Now high becomes mid minus one. That is three. We know. Again find out mid, the same process. So we have like it's zero plus three divided by two. It's one. Mid is one now. So mid right now is here. Now mid is here. And high is here right now. Compare. Is this five? Yes, this is five. We got it. It will return the mid because right now mid is this, so it will return one and that's it. So, we we have only in how many comparisons we got our answer? We have compared with this. This was the mid. One comparison and one like one and two. Within two comparison. Right? Now, case two is suppose we are having we you have to find out suppose 50. Now, key element is 50. See, again repeat the same step. Let's see. We are having our low is zero, high is again same eight, so same step mid find out zero plus eight divided by two that is four. So, now mid is here. Is this equal to 50? No. Yeah, this key element is greater than 50 mid element greater than 15. Mid element because it's 50. So, definitely we know that this would lie here. In the right side, the right half of the array. So, you have to modify now low. So, low becomes now mid plus one. Now, low is here. Now, low is four plus one that is five and high would be as it is eight. This variable or this pointer. Now, again find out mid five plus eight divided by two it becomes it would be six. Right? Now, our mid is here. This is now mid. Right? So, mid is here now. Now, see compare with this. 22, it's not equal to the key element. But, key element is greater than mid. So, we know that now we have to search from here to here. The right half. Yes? So, again the this low low is here. So, now this is mid, so we know that now it lie within this. This is the search space now, so low would be here, high would be here. So, now low becomes six plus one that is seven and eight. So, mid is seven plus eight divided by two. So, it becomes now what? Seven. Right? Because we are taking integer part seven. Now, mid is here. Low is here and mid is also here. Because we have only like two elements. So, low is same and mid is also same. Okay, fine. Now, compare. Is 50 equal to the mid element? No. Yeah, key element is greater than mid element. So, now we have to search in the right half. But, obviously the right half of this is only one element. One element left. Right? So, but obviously we have to go to the right half, so we again modify our low. So, low becomes seven plus one that is eight. I mean mid plus one that is eight. And high is still eight. So, now high is here. Low is also here. Pointing the same number, the same you can say obviously the element. Because our search space has been reduced to one. Now, again find out eight plus eight divided by two mid that is it's eight. Mid is also at the same position mid. Now, compare. Is this equal to mid? Yes. So, return mid. Mid is what? Eight, so it will return eight. And we know that at the eighth index there is 50. So, how many comparisons? One, two, three, four. In just only four comparison you got your answer. Right? Here we have 50. How many elements? Total nine elements. N is equal to nine. Even if N is nine but this is at the last and within the four I mean maximum you need four comparison and you got your answer. But, if you go for linear search you have to how many comparisons would be there? Nine comparisons because element is in the last. But, now third case is we want to find out suppose 500. Element is not there that can be a case. Okay, fine. Let's go for this. Now, we have low and high same process. Low is zero it's eight, so mid would be zero plus eight divided by two that is four. Now, mid is here. Let's modify this a little bit. Now, mid is again here. Is there target element equal to mid? No. It's greater than mid? Yes. So, our element would be in in this half only. We'll search here. So, you have to modify low. Now, low would be here. Mid plus one. Low becomes five. This is still eight, so five plus eight divided by two. It becomes again same process six. Now, mid is here. Right? Now, compare. Is this the target element? No. Target element is greater than mid? Yes. So, we would search in the right half only. So, again modify the low. So, low becomes again mid plus one that is seven. Six plus one seven. Seven and eight. Seven plus eight divided by two that is again we got seven. Now, mid is here. Now, is this equal to this? No. But, target element is greater than mid? Yes. So, it will definitely lie in the right right side of this mid. So, in the right half only. But, we still have only like search space is only one element. But, still we have to go to right. So, you have to modify your low. Low becomes mid plus one that is seven plus one that is eight. This is also eight. Eight plus eight divided by two. Mid is also here. So, right now low is here, mid is also here and high is also here because we have only one element. Now, see. Is this equal to this? No. Is this greater than mid? Yes. Means it will definitely to the right side. Yeah, right? Same process. One more step you have to repeat. If this is the right hand side, so we we do what? We modify low. So, low becomes mid plus one that is nine. Eight plus one nine. High is still eight. But, now see. This low is greater than high. Means we have moved here. High is here, low is here. Means it means that search space has been exhausted. There is no search space left with us. Right? We will search until this low is less than high or less than or equal to high. Once low becomes greater than high means there is no element to search in the array now. Okay? So, element not found in this case, so there would be no like we'll not find mid and all. So, here the loop will stop. So, you have to put one condition also to terminate the loop. While this low is less than equal to high till then we have to repeat these three four steps. Now, how many comparisons are there? One, two, three, four. Because we haven't compared here. So, this is the worst case. Means element is not there. Within you got this answer you got within four comparison. And this N is nine. You got it? So, there can be two three cases. This is how binary search works. I hope you got this why this is known as binary search and how the core concept of binary search. The algorithm basically. First step, find out the middle element. Second step, compare the target element is equal to the mid element. Compare the target target element with the mid element. If it is equal to mid element, return mid. If target element or the key element is greater than mid element, search in the right half. If target element is less than the mid element, search in the left half. Repeat the same process until you get your answer. Or you can say the search space is exhausted. Till then, that's it. Four five steps are there. Right? Okay. Now, let's code it a little bit. Let me just do just do practically if it's working or not. Then we will discuss the time complexity for this and how this is better than linear search in terms of time complexity. Right? Okay, so in this project data structure and algorithm we just want to create a new Java class and we are going for binary search. So, at first let's take an array. So, we got this. This is an array. Let's have a method binary search. And what? We are passing the array here and the key as well. Obviously you have to pass the key, so let's suppose you can take from the user also the number of I mean the elements in this array and the key using scanner object. You can just modify it. But, I just want to take the key is equal to right now just 10. Hard coded value. And we are passing the array as well as the to this. And it will return something obviously uh the int value. So, let's take a variable result. We'll store this here. Okay. Now, let's define this method. So, return type is definitely int. We are passing here one is array, so that is basically the reference. So, array and second is we are taking index. Same name you can take. It's ARR and here also ARR. Okay. Now, you have to take first what? The low. One is low and one is high. So, high we know it's whatever the length of the array ARR.length minus one. Yes, the index if length is nine then index would be at the last index would be eight. So, that's for sure we know. Now, you have to do what? Main steps are first you find out the mid, so int mid is equal to we have this low plus high. Now, we check. If we know the element is X is equal to whatever the element at mid. So in this case we simply return we know mid. But if this is not the case else if else if this X is suppose greater than a r of mid greater than this element in that case we know what happens if it's greater than you have to search the target would lie in the right half. So you have to change this low. Now low becomes mid plus one. Mid plus one. This thing we know. Right? Else if this is not the case then we know that if it's not equal to mid and this condition is also not true so definitely that element would be in the left half. So don't need to write else if you simply do high is equal to what we do high is equal to we change high now mid minus one. This can be a case. Yes. So we are done with this. Now this this is what these steps would be there is a condition to terminate these steps while this low is less than equal to high. Once it becomes greater than high obviously you have to stop means the element not found you have to print. In that case return minus one. So you have to put all these things we know within a condition while this low is less than equal to high. Till then you have to repeat these steps. Simple. Right? Otherwise if this condition is not true if low becomes greater than high then we know that at last the element not found and you have to return minus one simple. That's it. It's very simple. Okay. Now you have to call this okay we have called this function. It will return something so based on that you have to check if this result is not equal to minus one means we got the element and you have to print the index where you got the element. Element found at whatever the index it will return. Okay. If this is not the case in else you have to simply print element not found. That's it. Right? So let's try to run this. We we want to find out 10. So it should print 0 1 2 3. So element found at three. See we got it. Now you want to change let's suppose this key is 100. So 100 is not there so it will return element not found. It will run and see element not found. Now if this key is let's change it and it's two. So it should return element found at zero because two is at zeroth index. Yeah we got it. So it's running. I mean it's working. Okay if you want to check if you want to debug this you just have to do one thing you just add some breakpoint here and now debug this how it's running. If it's two and you want to debug this so let's debug this now. Debugging is very important. So it will definitely it's like dry run. You are dry running this on the this machine only on laptop only. Dry run means basically I mean you can do one thing you can just have just note down this thing on a piece of paper and then you can just try and that. You you have to be debugger in that case. But here you have this debugger. So in this case like control is here right now. So we have arrays this X is equal to two because you want to search two we have passed this two. E is two. Array length is nine. So array length is nine. Step over. Now low becomes low is zero and high becomes high is right now eight. So high is eight see. Let's step over. Now we have this thing. Mid is equal to this. Okay fine. Now let's run this. Now mid becomes four see mid is four. Right? Let's run this again. This condition is not true so control is in the else if. X greater than a r a of mid? I guess yes because you want to search for two. No it's not true. Because key is two I mean X is two. Okay and a r of mid a r of mid is it's four so 0 1 2 3 4 is 15. This condition not true so we'll go in the else part. So high becomes now mid minus one see. High is eight mid is four right now. But now high becomes three see. See the change. High is now three low is zero. So from zero to three we want to check now. Again check the condition while this yes this condition true while condition enter here find out the mid. Now mid is one. Right? Run this. This condition is not true because this was not one is five and you have to a r of mid a r of mid is five and you want to search for two. So this condition was not true else if X is greater than a r of mid? No this condition is also not true. So again into this else part and high becomes again mid minus one. So now high becomes zero low is also zero. Again run this. This condition is still true zero less than equal to zero yes. Now mid is again zero mid is also zero. At zeroth location I mean this. Now it's true. Now X is equal to equal to a r of mid because a r of mid is also pointing to here. Now it's this is true so it will return mid. Run this and see return mid means zero it will return zero. So now result is zero. Result is not minus one it's true so element found at zero so it will print on the console now. Element found at zero and then exit. That's it. This is how you can debug this. So this is basic like binary search. But one thing is if let me just tell you the overflow condition here. Now one thing we are writing what this I mean start plus let's let me just tell you here mid how you how you are going to find out mid? We are writing simply this low plus high divided by two. But this can be overflow condition sometimes. You have to modify it's not correct. Right? What we can do is suppose this low and high I mean high is sometimes suppose it's a very huge number. Let's suppose integer.max value. Whatever the max value. The max value is So this is we know that the maximum the range of the the integer max value zero to here. Uh not zero to here from minus two one something like this to this. 2147483648 I guess to this. We know this is the maximum value. In plus. Suppose high is this. And at one place at one time this kind of situation exist low also becomes this. Though both the low and high are the max value because in the previous case we have seen now low is also there high is also there at the maximum at eight. So there can be a case in this case also. Low is also this high is also this. If you are going to plus this with this then definitely it is out of the int range. So this is overflow condition. So that would be obviously in it will not give you some kind of thing there is that wrap up kind of thing. I have told you this thing. So by default it would be like negative value and it would store in two's complement and if you go to plus this this plus this again send it would store ultimately as minus two. Minus two divided by minus two it will give you minus one. Mid is equal to minus one and we know that minus one doesn't exist it's not a valid index. So this is overflow condition. If both low and high are huge number if you are going to add these both these numbers then definitely it would be out of the int range. That is overflow condition. Now how to handle this? Obviously we have to find out mid for mid you have to do this thing. You can write down the solution is you can write down this thing. One way is you can just take this mid and these as a long. That would be in range. But better is why to take long and we know that we don't need that much kind of thing. That long data data type. So we can do one thing we can just write down this thing in a different way. So we can write down this mid is equal to something like this mid is equal to low plus high minus low divided by two. This is also as it is like same as this. It will give you the same result because we know if you are going to compute this then LCM is two and two into low plus high minus low and ultimately it becomes low plus high divided by two. This is the thing. But in this case it will not give you like that overflow condition. If this both are same then low is this plus high minus low we are not going to add we are going to minus. Then it becomes zero then low by divided by two and you will be within the range itself. If both are huge number. So rather than writing this better way is while you are going for binary search algorithm better to write this. Okay. And in interview also don't directly write down this write down this condition. They know that okay you have the idea about those overflow conditions. That's why first I have just written this thing and now why the cases I'm telling you that overflow cases and you have to switch to this condition. So now you can modify your binary search program. Rather than this you have to write down this thing. You got it? Overflow condition you got it? Now discuss about let's discuss about time complexity. Okay. In linear search we know it's order of n. In binary search it's log n, but why log n? See. We we know that suppose we are having n elements at at first, right? So at first there is no comparison. At first. Right? n elements are there. Now in the second step you do you find out mid? mid mid is here. So we have divided this in this half or I mean two half. So we know that our element if it's mid, so directly it will give you the result. So that is the best case means order of one. Only one comparison you need. We know that time complexity while going for time complexity we basically focus on the number of comparisons you have done. Right? So you have to find out maximum number of comparison for worst case complexity. Got it? Okay. Now we have divided our space in two half. Either you will search in this or this, but definitely in two half. Suppose we are going for this half. Mainly right now it's n, so here we have n by two. This is also n by two. So this is n, this is n by two. Search space is now reduced to n by two. In the next step it's again it's again divided. We know. So now element would be either in this half or this half. So we have divided into n by two divided by two. That is n by four n by four. So it becomes n by four. And in the next step it becomes n by eight. Because again we divide this something like this. If you are having this then again we divide this into half. Suppose element is there, so again we divide this into half. So this becomes like n by eight n by eight. n by four divided by two, so it's like n by eight only. Right? Like this we are going. Right? Now see ultimately ultimately at the end we will reach to like the search space will becomes only one. In the worst case if element doesn't exist. We know in the previous case I have shown you. At last you get that there is only one element and you have to search there. The search space is only one element you have. So only one. So it's one. Like this we are going. So like this we are going from here to here then here then here and here. So here there were no comparison. At first at first we haven't compared anything. We compared after dividing it. We are comparing after finding mid we are comparing with this. We know. At first we are having n there is no comparison. So zero comparison. Here we are having one comparison. Here till now we have done one comparison this and one with this mid. So basically two comparison. Here one was this, one is this and one is this. So three comparison. Like this then four comparison. Like this. Right? So can I write something like this? It's n, so n divided by two raised to power zero. n divided by two raised to power one. n divided by two raised to power two. n divided by two raised to power three. Here zero comparison, so n divided by two raised to power zero. One comparison, so n divided by two raised to power one. Two comparison. n divided by two raised to power two. Something like this. Right? Then three comparisons. Then or you can say in level three n divided by two raised to power three. So this is equal to two whatever the power you have of two it's equal to the number of comparison. At last we got one space. So suppose here we have done like it's kth level or k comparison. Up to this we have done k comparisons. So can I write this one as it's n divided by two raised to power k? With the approach whatever you have done with the pattern. Right? Because we have zero comparison, so we can write n divided by two raised to power zero. So ultimately after some comparison suppose kth comparison we got search space one. So can I write with the same pattern one is equal to n divided by two raised to power k. Simple. It's a little bit mathematics. So we can write one is equal to it's not that much tough. If you are not getting this n divided by two raised to power k you just watch this video again a little bit. It's not tough. Okay? If you go through the this pattern then you will easily get why I'm writing one is equal to n divided by two k. Now how to solve this? It becomes two is equal to two k is equal to n. While solving this so ultimately you we have to find out the value of k. To find out the maximum number of comparison. Because we know that after kth comparison we got this thing. So you have to find out k. Means in the worst case how many comparisons you required? And that would be your definitely the time complexity. By ignoring all the other constant and all. Ultimately generally we know that we we consider that the number of comparisons only. Okay? The number of operations or the comparisons. Right? Now we have to find out value of k. So how to find out? In this case if you are a little bit aware about maths you to find out this type of value we take log on both side. So take log on both side. Once you write down this so k will be here and it becomes log two is equal to log n. And if you find out k then k becomes log n divided by log two. And you can just write down k is equal to log of n base is two. Divided by two then we can write down this something like this. Now these many comparisons. Or maximum and sometimes you get number of comparisons are this this plus one. But we ignore that one and all while writing big O notation. So time complexity would be log of two n. Because in this case in the previous case I have shown you we are having almost nine element. And if you have nine or 10 elements suppose 10 elements then maximum you need four comparison. Four or five. That's it. Okay? Uh two in the worst case. And if you get log value of 10 it's approximately four. Log value of 10 base two. If you get like this thing log of 10 base two it would be 3.9 something. So it's like four approximately. And at most in worst case if 10 elements are there and the element is not present there you will need four or five maximum five. So the number of comparison maximum is four plus one. I mean log of 10 plus one. That's it. You get the result. You get the answer. And we ignore this one. So in big O notation we write this thing. You got it? Now if there are 500 elements then uh maximum because we are if you have 500 element if n is equal to 500 so we know that in linear search in worst case 500 comparison you need. It's order of n. But in this we are dividing this by half. So this is one comparison. We have compared this one comparison. Now plus either this or this you have to search. So you have divide the space by two 250 and 250. So suppose element is at this side. So again divide this by two. So one comparison is this. One comparison. Again you have removed the this it's would be 150 125 or 125 search space. Again divide this. In worst case I'm telling you. Right? Again divide this. Now one more comparison you have done with this mid. Now again you have divided this. So it's almost like maybe 62 and 62. Or 63. Right? So like this you again divide then at most in worst case you require nine or maximum 10 comparison to get the result in worst case if element is not there in this list. So you need in 10 comparison suppose let's say 10 comparisons you get your answer. In linear case you have to do 500 comparison. If suppose data set is having 1 million data. So linear search you require 1 million comparison. And here a 1 million in this case log of 1 million you can just easily find out on the Google. It would be really less. Okay? So now you I hope you got this why this one is better. And log of if you get log of 500 it will give you almost approximately nine 8.92 something like this. So approx nine. So the number of comparisons are nine plus one. That is 10. So log of n plus one number of comparisons maximum. Okay? That's why now if you are aware about this this log values and all then you can easily find out that how your graph is going on. Like this graph the time complexity graph. Number of comparison number of operations or the size of input size. So how this is going? It's basically something like this. Sorry it's logarithmic. So it's something like this. Linear is something like this. Something like I mean linear a line. Something like this. Let me just draw this again. Linear is we know something like this. But log is something like this. Something like this. So there's a huge difference when when the data would be increasing. See. In the number of operations there is a huge difference. So that's why obviously log n is better. Right? Now you got now why time complexity is of log n and why it's better than the linear one. Linear but the a prerequisite is here the data must be sorted. But now we have seen the data was in ascending order. See. Data is in ascending order. We know uh data is in ascending order so we have done uh we have write down our code. But what if data is in descending order? Now you know that data is in descending order the array is in descending order. Now how to apply binary search? Very simple. Suppose this is the data. This is in descending order. Yes? So same approach you have to apply here also. And in advance you know the data is in ascending order. So we have only nine elements and this is our low same this is our high. Again you have to find out mid. So mid is definitely we know this would be mid. But now if key is suppose I want to search for 22. You have to change this condition a little bit. You can just pause the video and try this out. This is the array descending in descending order. I want to find out 22. You have to apply I mean binary search definitely how to get how you know the logic. You have to change a little bit. Now if it's 22 then see check with mid. This is five this is 22. It's not equal. Now we know that our key or the target element is greater than our mid element. So in the previous case if it's greater than then you have to search in the right half we know but it's in descending order. We know that mid is five so definitely on the right half elements would be either five equal to five or less than five. 25 would not lie in this part right half. So in this case now you have to search in the left half. Now high becomes this. So now high you have to change. If this is greater than then high becomes mid minus one. If the key is suppose two. So this is five it's not equal but our data is less than mid. So we know we already know in advance that array is in descending order so we know that the data would lie in the right half only. So we can change in that case we change low is equal to mid plus one. A little bit you have to change. Right? Now let's uh let me show you practically this thing. So let's take a new array and we are going for now that is descending order. Suppose we have an array ARR of one. This is in descending order and this array is ascending order. Now I want to apply I want to uh here pass this array of one array one. ARR1 this array which is in descending order. Now you have to change this a little bit. Now what to do? Low and high while less than low this condition would be as it is mid would be as it is. If this is mid return mid but this condition would check if x is greater than now array of mid then now you have to change here high becomes mid minus one because array is in descending order. Else you have to change comment out this. Else low becomes mid plus one. That's it. And that's it. We are good to go now. If the key is two so two let's run this and see. What output you will you will get here? 0 1 2 3 4 5 6 7 8. So element found at eight. You got it? If this key is suppose uh 22. So this is at 0 1 2. So element is at two second index. We got it. So I guess that's not that much tough. Right? But one thing now okay I I guess you got it. Time complexity would be as it is but for more cases there let me show you. So we got the time complexity as well in best average and worst case. We don't consider generally average case we go either go for worst case or best case. Okay? But in average and both worst case it's order of order of log n in best case it's order of one itself. Now overflow case is also I have told you. If you do start plus this then it would be overflow out of int range so better to write down this thing. Now now next thing if in advance you don't know array is ascending or descending. In that case how you will go for binary search? If you assume that like obviously array is in we assume when you go for binary search we just take simple example array is in ascending order and we apply that thing. But if interview ask like interviewer ask you don't know array is in ascending order or descending order. That is for sure one thing is it's either in ascending or descending order and you can apply binary search easily we know how to apply binary search when array is in ascending and descending order both the things we have seen. Both the logics now you know but at first you have to find out now how to check first. So the solution is you have to apply now order agnostic binary search. In this case first we'll check array is in ascending order or descending order and then we apply according to whatever the situation if it's ascending order that logic if it's descending order a different logic the conditions. The logic is same only the condition is a little bit different. That's it. Okay but first how to find out that is a crucial part. Now if suppose array is something like this. How to find out? Maybe you say that just pause the video and think about it a little bit. How you will get to know that array is in ascending or descending order? Maybe you say okay compare this with this. First element with second element. In ascending order if this element is greater than the first element we know that this is ascending order. Because if it's greater we know that all the elements would be greater than this. And then apply the logic. Okay fine. Let's suppose it's 10. Both the elements are same. Then we can't simply compare this and because these are equal. So it can be ascending or descending order. It can be case if it's it is also 10 in that case. So what is the best scenario? What what are the best two numbers you can compare to find out that it is ascending or descending order? Think about this. So the best element to compare are this and this. First and the last element. If all the elements if this is 10 then the 10 10 10 and this is 10. So we know that obviously in in array we are having only one element that is 10 itself at all the positions. But the best two elements to compare are this and this. If this this last element it is greater than the first element then we know that it is in ascending order. If the last element is less than this then it is in descending order. Equal to lie in either descending or descending case. Okay? So how to check? We can check like uh we can have a variable. Now while applying for the condition now you have to check if it is in ascending order apply these if else. Otherwise apply the descending case if else. So first you have to check. So we can take a something like a boolean variable boolean is ascending. Right? At first maybe you can set it false. And now you check. If ARR of low if this less than ARR of high this element then we can set this is ascending is equal to true. Simple. And while applying those conditions you check if is ascending is true apply that case. Now uh if it's less than then it's ascending if it's equal to or less equal to or less than I mean equal to or greater than this element then it will lie on the second case that is descending order. You got it? Now pause the video and try to write down a program for this. I guess you got it. First you have to determine the order then you have to apply the logic accordingly based on the array order and same continue you know the normal binary search process. We know the binary search process same thing you have to apply. Okay. Let's now practically see this thing. So what we can do is let just create a new Java class here. It's order agnostic binary search we are discussing so same array let's take we have let's change the name of the method it's order agnostic binary search. We are passing here ARR1 that is descending order but obviously we we will check first. So let's define this method here. So we know the same thing first we have we will have low and one element sorry one variable is high that would be we know array of length minus one. Then we have to find out uh if it's ascending or descending. So for that we can take a boolean variable, boolean is ascending. Let's not initialize it. And what we can do is here if it is true, then we can assign it true. If it's low is less than a r of I, this is true. Simple. So, now it becomes true. Otherwise, by default we know that it would be false. So, otherwise else or you can say else it's false. So, we can simply write here is equal to first false. It will change it, otherwise it would be false as it is. False. Okay. Now, let's we know the condition now. Uh that would be low less than high. Till then we are going to repeat the steps of binary search. Got it? Now, what you need to do first obviously we have to find out mid. So, mid would be it's now low plus Sorry. We know high minus low divided by two. This is the mid. Don't just do low plus and bracket this bracket and divide by two. No, it would be it would be wrong. It's simply high divided by two every time. Divided by two is only high minus low divided by two. Low is separate. So, we have calculated mid as well now. Now, check. First check if rather than write No, checking if it's ascending or descending. We know that first one case is common in all the cases if array is ascending or descending. If it's array of mid is equal to or whatever your element x is equal to array of mid, in both the cases, then definitely it will return. This is the common case. Is equal to array of mid? Double equal to Sorry. Then it will definitely return mid in both the cases. So, this is the common case. Right? Okay. Fine. Now, check it's ascending or descending order. Because whatever condition now you apply, it depends on the type of array. So, now if this is ascending, if it's true, in that case we check. Means it is in ascending order. Ascending, right? If it's true. Then we check if your x is we know greater than the mid, then we know that the element is in the right half because the array is ascending. So, we have to change the low. Now, low becomes mid plus one. Simple. Right? Else, we know you have to change the high. So, else high becomes mid minus one. Very simple. Right? So, this is else part and this is if if it's true. Now, after that else, we know in else we know that if it's not ascending, it would be in descending order. So, apply those thing. If let just copy paste the same thing because you have to change a little bit here. So, if this is greater than array of mid, now here you have to write down this one. Because array is in descending order. And here you have to change low is equal to this. Low is equal to mid plus one. I hope you are getting this. It's not tough. Right? So, this is descending case. Otherwise, if uh the element is not there, then after completing this while loop, while loop is ended here. See, this is closing of this while loop. After while loop, we have to return minus one. So, simply write here return minus one. Very simple. That's it. So, if you didn't get it, just pause the video. Uh write down this code on a piece of paper. Dry run this. Okay, you'll get it. Now, I'm passing here now at this point of time a r of one, a r of one. And I'm just want I just want to check 22. Where is 22? Here is 22. Let's run this. And it will give you 0 1 2. So, it is second index, 0 1 2. Yes. Now, 22 is here itself in array a r of one. It is in ascending order. Now, let's pass the array a r r, this array. And again, same search for 22. So, let's run this. It will give you 0 1 2 3 4 5 6. See, element found at six. Means the logic is correct. In this case, it's at 1 2 3. It's In this case, it's it is at six location. So, both arrays you can pass and you can check. You can find out. So, you if you if you're not getting this, either you can debug this code. In this case, if you want to debug this, suppose right now we are passing this array. Right? So, you can just debug this. You can just We know how to debug. Add a debugging point here at the breakpoint here and now debug this. So, array is this. Array is this. The variables are x is 22 and array length is nine, we know. Step over. Now, we know that high is here. Low is zero. High is eight. Array length is nine. Array of low is two. And array of high is 50. Boolean is is ascending is false right now. Check the condition. Condition is true or false? Let's run this. Now, its condition is true. So, it becomes true. See, is ascending is right now false, but as soon as I step over, it becomes true. See, it's true. Now, this condition is also true. Calculated mid. Mid is equal to four, we know. Now, run this. Now, is condition is ascending was true, so control will go in this if else statement. See, it is true. So, we are going to enter in this loop, in this if condition. Right? And then we definitely get it. So, you can debug this right now and x is 22. A r of one is this. It will give if you run this, so it will give you a result. Element found at six. Right? After passing a r one, you can again debug this and you can check. It will not go to into this if part. It will go to into into this else part because at that time is ascending is false. Now, if you don't want to write down this in the two three lines, we can simply write rather than this. What we can do is is ascending is equal to write down directly you can write down this condition. So, let's just write down rather than false here. This condition as comment out this thing. Simple. So, it will return true or false. Based on that, boolean is element would be assigned the value. Simple. Right now, if you run this, same it will give element we are searching for 22, so it is in 16. Uh sorry, sixth position. So, you can write down this thing in same one line itself. Or if you're not comfortable in this, you can just go for those two three lines. Right? So, this is order agnostic binary search. So, we got it this thing. Now, why binary search is better? We know the speed. It is it significantly reduces the search time because the number of comparisons are less. Time complexity is order of log n. And you know, fewer comparisons, so that's why it is more efficient than the previous case for large data set. If you have small data set, 5 10 50 elements or 100 elements, you can go for linear search, but for huge data set, 10 suppose 10,000 element, 1 million element, then go for binary search. In that case, you will see the difference in the obviously the time taken by to by executing that program. Advantages we know it's efficient because of log logarithmic time complexity. Then it is ideal for large data set and it's not that much tough. It's easy to understand. It's not that much tough. Drawbacks, one is prerequisite is you have a sorted data. It will not work on unsorted data. If there is unsorted data, you have to sort it first, then you can apply binary search. Okay? Insertion and deletion as little bit not it's efficient for frequent data modification. Because uh yeah. Uh see, I'll show you how to insert and delete if the array is sorted. Uh when when you go for those uh you know, you have to find out there duplicates element in the array. And you have to find out first occurrence and the last occurrence of that element. In that case, if array is sorted, we go for binary search. So, for that we apply our another technique like lower bound. We find out lower bound. We find out upper bound in that case. So, we'll show I'll show this I'll show you this thing in the next video. But it's not definitely good for frequent insertion and deletion. Okay? This is one Java code for binary search. We have seen this thing. Some real world example, while searching in the databases or the large data structure like B tree and B plus trees there, binary search is being used to search. Okay? In dictionaries, while spell checking, in that case also binary search is used. Competitive programming, coding interviews. Uh this is the question you have seen. I told you find the first occurrence or find the number of duplicates. Find the last occurrence of this letter of this element. So, there are so many lead code questions or code code chef or there are so many coding platform. There you get many questions uses binary search. You can solve those questions by using binary search efficiently. There can be many approaches, but efficient approach is using binary search. In internet like router used if you they want to look up the IP addresses from the array and the IP addresses are in sorted order. So, uh there binary search is being used. In e-commerce and online libraries, they're searching for books on Amazon or any library databases there, this is being used. In Git also, uh if you want to find out the commit that introduced a bug in the Git, so Git bisect, then uh there binary search, this algorithm is being used to find out which Git has introduced this bug. Which, sorry, commit has introduced that bug. So, there are so many applications of binary search algorithm, real-world applications, okay? But ensure that the data is sorted while applying this thing, and you have to handle the duplicates as well. If the array is having some duplicates, if suppose this is the case, I am having uh this array. There are so many duplicates in my array. Suppose I'm 2 2 2 2 2 and 3 4. Now, I want to find out for 2. I want to search element 2 exist or not. So, linear search will give whenever it find the first index, but binary search will give you divide by half. So, we have it's 7 by 2, I guess. 1 2 3 4 5 6 7 8. So, 7 by 2, three. Middle is this. Binary search will give you index three, linear search will give you index two. So, like this. Okay? But yeah, if the duplicates data is there, then we have to follow another approach. So, you have to handle this thing carefully. In this case, you can go for um lower bound. If this is the case, then go for lower bound as well. Where at first occurrence, where is the first occurrence of this two? You definitely, if you go for lower bound, then you will get at zeroth index the first occurrence of two is there. Or you can go for the last occurrence if you want to find out, then go for the upper bound. So, here you will get the last occurrence. Okay? I'll show you in the next uh lecture how to implement this lower bound and upper bound in binary search. Don't worry. Okay? So, this thing we'll see uh in the next lecture, but basics are I guess clear to you. Binary search, why it is better than linear search, and what is order agnostic binary search. But if we have duplicate kind of data, then how to apply binary search and these things, that thing we'll see in the next lecture. Right? So, I hope now everything is clear to you, whatever we have discussed in this lecture. Now, I'll see you in the next lecture. Till then, bye-bye. Take care.