DSA-Discussing All Search Algorithms With Interview Based Questions- Ft: Priya Bhatia

Key Takeaways

hello everyone welcome to the session so now i think it's the right time to discuss about the applications of an array as we already discussed about the fundamentals of an array pretty well right okay so whenever we are talking about an array data structure there are a lot of things which came into picture for example usually i think when i talk about error data structure for the first time in my video i told you that whenever we want to do searching operation in an re uh searching operation array is quite useful right why because a random access is possible inside that array so the very first thing which we will discuss in today's session is about the searching concept in an array so searching in an array now the searching can be usually have two things here one is simple linear search which we will already study also when i was talking about the implementation of an array data structure in python if you remember we already had a talk about the linear search but as a brief context i'll again give you in this session what is linear search because now as a proper topic we are talking about the searching algorithms and second one that we will talk about in our upcoming sessions is the binary search is the binary search which you can say is an optimization of the linear search that we have but before going into these algorithms let me talk about it what is simply searching algorithm so it says that for example uh adding is provided to you and an array contains a lot of elements okay so for example here i am defining some sort of array here which contains the elements like 20 40 70 10 12 11 29 75 46 like this so here if you will see the number of elements that we have by default starting index will be 0 then we will move towards 1 2 3 four five six seven and eight so here in total we are having nine number of elements that we have okay fine now basically suppose you want to search for any element present inside the array suppose we want to search for any element which is present inside the array so what will happen here is that that searching algorithm will helps us to find out the index of that particular element for example suppose i am saying that i want to look for the element 11 that this element 11 is present at what particular index so what linear search will say it says that okay it's quite simple i will start from the zeroth index i will keep on checking that the element that you are looking for is equals to the element which is currently present inside the array or not if yes i will return the position if not i'll simply keep on traversing until i will reach to the end of the array that's the simple concept behind the linear search i will say okay what it indicates it indicates that there must be one for loop which will start from 0 right and will go until the length of the array suppose n is equals to whatever be the length of the array that we have now we are just checking that if the value which is currently present inside the array so what i am saying is that this range function with the help of this range function my value of i will start from 0 and will go until the value of n minus 1 here so if the value of the error of i which will start from 0 and will go until n minus 1 is equal equal to the element that we are looking for in that particular scenario it will simply return the index which is the value of the i if suppose we are completely traverse the complete loop starting from 0 to n minus 1 but still we are not able to get any element which is we are looking for because it might be the case now where suppose a user is looking for an element suppose 47 which is not at all present in the complete array that we have right in that particular case when it will go out of the for loop it should return to me the value as -1 so basically the minus one indication is simply says that element is simply not present in an array element is not present in an array so that is a simple thing that we have here because linearly we are starting from the very first index which is zeroth index and we are going until the value of n minus 1 that's why this is something which we can say is having only single for loop and that's why the time complexity if we will talk about in worst case scenario how much what do you think in worst case scenario what is the time complexity for a linear search it should be for sure order of n it should be force your order of n because consider what is the worst case scenario worst case scenario meaning that suppose a user is looking for some element which is not at all present present in an array in that particular case user will traverse the complete array and still the user will not able to get the position of an element and then finally after traversing the complete array it is returning -1 or maybe user is looking for an element which is present at the very last position or almost last position again at that point of time if we are applying a linear search in worst case scenario it will go until order of n i hope i am making sense to everyone if suppose i am talking about a best case scenario in this particular case so what do you think in best case scenario for a linear search what is the time complexity first of all think that what should be the best case scenario here best case scenario says that it might be the case that the element that you are looking for is present at the very first position and when the value of i is equal to 0 it automatically returns so at the very first iteration itself it will be able to find out the index of an element or maybe you are looking for an element which is present near to the very first uh position or near to the very first element which is there for example 40 for example 70 so suppose you are having uh maybe one lakh elements and inside that one lakh elements in the top 10 positions you are able to get an element it means that you you you are not traversing your complete for loop until n number of times so at that point of time you can say that your time complexity will be order of one so what is the meaning of best case scenario when your element is present when the element is present at initial indexes what is the meaning of worst case scenario in specifically i am talking about a linear search in this particular case when we are seeing worst case scenario it means that element is present almost at the last index so here the element is present at almost last index right this is the best case scenario and this is the worst case scenario okay what will be the average case scenario so what do you think what will be the average case scenario for a linear search algorithm right so that's why i'm discussing this in a separate video and because i have already discussed i know the linear search code also i have written but in depth we are discussing in this proper separate session that's the need for this session okay and it's always the flow like if we're discussing about searching algorithms it should be there so that you can't skip any any important thing in any of the videos okay when we talk about average case scenario when we talk about average case scenario what does that mean simple meaning is that that element can be present maybe at the first position maybe at the second maybe at the third maybe at the fourth until so on may be at the end divided by how many number of elements do we have because we need to take the average divided by n now this series is something which can i say is a sum of n natural numbers sum of n natural numbers that we have right so we can write this as n into n plus 1 divided by 2 divided by complete n and this will be cancel out with each other so we will be able to get the in terms of uh average case we will be able to get the time complexity as again order of n it means that in a linear search whenever we are talking about worst case scenario time complexities order of n whenever we're talking about average case scenario then also time complexities order often but when we're talking about best case scenario it means when the element is present at the very initial indexes may be 0 1 or 2 something like that then in that particular case obviously my element is not iterating completely at the end of the array so that's why it will be order of 1 which is a constant based time complexity that we have now i think that you will be easily able to understand this part implementation wise we did already the implementation i am just showing to you uh just a brief uh recap because we already have done this task so here if you remember while doing the array data structure implementation the file which is already shared with you in that video you will be able to observe this code which we have written live only i have written this code live only where we took the array right then what element we are looking for then we are calling the function we are calling directly the linear search function which is containing the array which is containing the element that we are looking for and we are storing whatever whatever be the result of this function inside this variable called result now this is very important the function definition is very important where we used to write the uh basic code basic logic behind the uh operation that we want to do here so here it will take the array here it will take what element we want to look for and now we are starting our for loop which i was stated earlier as well so we are starting from by default 0 and it will go until the value of n minus 1 we are simply applying one condition here that the element that we are looking for is that element is present in the array or not if yes return that element if not and if suppose we will be able to completely iterate one for loop return the value as minus one so minus one is indicating that the element that you're looking for is not present inside the array now if you will run this code you will be easily able to get the value as 5 because here if you will see 15 is present at index 5 why because by default index will start from 0 so it will be 0 it will be 1 2 three four and five so finally the return statement will give us the five as the result and that's why it's showing now here in that video also i have showed you that if you enter some number uh which is not belonging to this particular value at that point of time it will show -1 for example here suppose i'm mentioning 20 so here it is not present inside the array that's why the output is -1 and that's what i have illustrated in the complete video that we have done so far and in this video we have discussed about time complexity in very much depth what is about the space complexity part what do you think should be the space complexity for this particular code it's quite simple we are not using any kind of extra space here and because we are not using any extra space so the space complexity will be order of 1. always remember if you are using any extra space apart from the given array that you have then your time complex sorry space complexity will always be constant okay so this is all about the very first searching algorithm that we have in an array which is a linear search in the next upcoming video i'll talk about binary search which is a very amazing algorithm and is very important in terms of interview perspective also and in terms of practical real-time applications as well we are using binary search quite a lot here if you will see in linear search we are getting in worst case scenario the time complexity is order of n now developers think a lot and they they want to optimize this time complexity which is order of n so they explode and find a way which is a binary search which works pretty well and is able to get a time complexity which is very far less than the order of end time complexity how is that so what's the logic behind that i know you all are curious with me so we will discuss this in the upcoming video where i will talk about binary search in very much depth we will try to understand that part and then we will try to go step by step towards the recurrence relation in the time complexity for the same now i think you are going towards the advanced portion of dsa so i hope that you all are enjoying this course so far we have discussed that what is linear search and we did a deep analysis on the complexity part as well right and we have seen that it usually took order of end time complexity in worst case scenario to go for a linear search based algorithm now in the in our next part we will talk about something called as binary search algorithm and as i told you this is one of the most important and very you know interesting application of and searching algorithm and it's quite useful as well why because for sure it is giving us a very less time complexity as comparable to the linear search that we discussed until now how is that so how internally this is working we will talk about that now binary search is usually an application of divide and conquer now don't get worried if you don't know what is this we will discuss in very much detail with a lot of applications of this divide and conquer algorithms but as of now just try to i'll try to give you just brief brief overview for those students who are not already aware about this concept of divide and conquer it says that practically if suppose the problem is very big so what we are trying to do in this particular divide and conquer approach is that we are trying to divide our problem into sub problems and we are trying to conquering each sub problem pretty well and then we try to merge the solution this is the overall idea behind divide and conquer if you're not able to get an idea clear cut just wait uh for few more sessions uh after that you will see that there is a appropriate module with the name of a divide and conquer and there we are discussing a lot of applications and after discussing all those applications i believe that you all will get the expertise on this particular module as well but as to get a sense of this let's talk about binary search so it says that what we will try to do is that suppose you're having a element so first of all this binary search says that i will only apply when you give me a sorted array so the very first thing which we have to keep in our head that whenever we are applying a binary search the array should be in a sorted array the array should be a sorted array it means that for example you are having something like this in increasing or decreasing fashion doesn't matter so here i am taking an example of increasing order array that i have for example i am having 2 i am having let me write somewhat bigger so that you guys will not face any issue 2 4 8 12 20 25 maybe 50 and 70. suppose these are the elements that we have in our array by default the index will start from 0 so it will go 0 1 2 3 4 5 6 and 7. so this is the error that i have right and these are the indexes that are given to us okay now suppose uh first of all you can clearly observe here it's a sorted array suppose i want to look for a position for an element 50 whose position is 6. so what i am saying is that i am searching for an element 50 here so how basically this binary search approach will work that's what we supposed to see here in this session so first of all what's a small problem here what should be the small problem in this particular scenario you can say that small problem is something when i am having only a single element because when i am having a single element in an array so at that point of time only one if condition is required for example if suppose i am saying that this is an error that you have which contains only 50. only single element is there now what you can do is that suppose you are looking for a 50 only so you will just have to apply only one condition that if the value which you are looking for and the value which is present in your array is equal equal to x there is no need even to apply any for loop here if yes you can simply return the value of i otherwise you can simply return the value as -1 because there is only one element which is present so there is only only one condition that we need to apply here that is pretty much fine but if suppose we are having more than one element which is a practical scenario right we usually don't have a single element in an array if we want to store any single element then why there is a need for an array right array basically stores multiple elements right because if we are we want to store any multiple elements it's not like that we will create other variables it's like 50 elements 50 different variables no at that point of time only this error data structure need will come right so it means that when the problem is a big problem means by saying that when the array size is quite big at that point of time what we will try to do using a binary search we will try to find out first of all the middle value middle index so how basically we will be able to find out the middle index we can take the there are two ways so first of all i is the starting index that we have which is 0 in our question in our example and j is the ending index that we have which is 7 in our example so one way to find out the middle value is we you can directly do what is the value of i what is the value of j divided by 2 simply this is how you will be able to find out that what is the mid value for example here you are saying 0 plus 7 divided by 2. so here it will take the lower bound and you will be able to get the value as 3 it means that this is the value which it is considering as a middle value this is the very first step that you have to do another way to calculate the mid value is the same way but the approach is different i plus j minus i divided by 2. now the question is that which particular approach should we use this one or this one while evaluating the mid even though you will get the same answer so here also the value of i is 0 the value of j is 7 7 minus 0 is 7 divided by 2 it will be equals to 3 but i would say the best approach is to go for this way why i am saying this because usually what happened is that it might be the case that the summation of i plus j is very much high that it will cause a problem of overflow right at that point of time this particular way will be the cure so by default always make a habit to use this kind of approach to always evaluate any kind of a middle value now once you will be able to calculate the middle value what you can do is that why it is called binary because here we are dividing our array into two halves how is that so let's try to understand this now so here uh if you will see we are having i'm writing it again the array 2 4 8 12 and then i am having 20 25 50 and 70. 20 25 50 and 70 and the indexes are 0 1 2 3 4 5 6 and 7 this is the indexes that i have now here the element that we are looking for is i think 50 only fine so what i'm saying is that you need to evaluate what is the middle value that you have so the middle value that you are getting is the 3 right what is the next task the next task the second step is to just do the comparisons now is the value of r of mid is equal equal to the value that we are looking for is this condition satisfied suppose you are looking for an element 12 only at that point of time for sure you will say that this condition will be satisfied and you can directly return the index which is mid which is 3 right but as of now our question is not to get the index of the 12 but to get the index of the 50. now in this particular case we came across two possibilities maybe you are looking for 50 or maybe you are looking for something called as 4 means either you are looking for a value which is less than r mid or you are looking for a value which is greater than r mid because the array is already sorted the array is already sorted so either the element that you are looking for will be greater than the value of the armed or the element that you are looking for is less than the aramid means are you looking for 450 consider that the element that we are looking for which is the value of air of mid is lesser than x so the element so this is the condition so suppose we are looking for 50 and air of mid is giving the value as 12. this condition is satisfied right once this condition is satisfied at that point of time you need to see that now which side you should go can i divide my search space into two halves now so here the answer is yes the answer is yes why is that so because here the array is already sorted and i am looking for a element which is greater than the aramid it means that the element will be for sure present at the right side of the aramid so what we can do is that suppose here you are calling a function by the name of a binary search which is simply taking the value of an array which is simply taking the value of the value of i as 0 which is simply taking the value of js7 initially right and the element that you're looking for is x means your function which is the by the name of a binary search is taking the initial values as add the value of the i the value of the j and the value that you're looking for but now what you can do is that you can call a recursion now what is recursion recursion is simply calling the same function again inside the method definition but with different set of parameters so here what you're trying to do is that you are trying to call this binary search function again because you want to do the same task again but now note on the complete array which you initially passed as the main function but now you will change your method definition by saying you will pass the array you will see that now don't start with the value of is0 start with the value of is mid plus 1 because i know that the 50 will be present towards the right side of the 12. 50 should be present at the right side of the 12 because the elements that i am looking for is greater so here instead of passing the value as i we are passing something called as mid plus 1 and then we will go towards j and the value x will remain same so this is something where you can say you can call the recursion and you can do without recursion as well by simply changing the value of i as mid plus 1 or what you can do is that you cannot call the recursion but you can change the value of i as mid plus 1 simply so this is a kind of a pseudo code which is applicable for all the programming languages which you want to solve which you want to use but here what i want to describe is the logic that what is the logic behind the binary search how internally it will work now this is the one scenario another scenario can be that the element that you are looking for is 4 it means that the element that you are looking for is lesser than the value of air mid means armed is having a value of 12 but you are looking for 4 this condition will be true at that point of time again you are pretty sure because the element that you are looking for is less than the value of air made i will go for the right left side of the armad it means now at this point of time which parameter you will change you will change the value of j which will become mid minus 1 because now you know that there is no need to traverse at the end of the array i should traverse until the value of the mid minus one so here what you will try to do is that if you want to use recursion then you need to call the same function again just like the way i did above where binary search here you are saying add here you are saying the value of i you are passing the value of mid minus 1 and the value of x or if you don't want to use any recursion you can simply say the value of j will become mid minus 1 and that's it that's it until unless your value of i is less than the value of j and you are making uh these conditions if they're satisfying for sure you will be able to get the index if it's not satisfying at the very end once it will be able to traverse the complete array you can return -1 which indicates that the element is not at all present in an array but now here the one thing that you need to understand again this is something which is recursion calling the same function again but with different set of parameters now one thing one thing which you need to understand is that that at each and every time we are dividing our search space into two halves we are saying to our code that don't traverse complete array just like the linear search we are saying that either you should go towards left side of the array or you should go towards the right side of the array either you should you should go towards the left side of the mid or you should go towards the right side of the mid and accordingly we are solving our searching space and that's why i would say there is a need of a sorted array if suppose the array is not sorted then how my code will be able to decided that whether i should go towards left or right there is no way that's the only logic behind saying that there should be a sorted array whenever we are applying a binary search by saying that you need to understand logically why is that important why we are seeing that aspect that's the very important thing that you need to understand here there are a lot of interview questions which you can face on this concept this concept is pretty easy but they used to modify the questions a lot and obviously in this in this course we will discuss each and every aspect of the interview based questions as well but before discussing those things it's a preliminary thing fundamental should be strong you should logically and as well as practically able to implement everything before we will move ahead towards the other part of our video i hope that i am making sense with the logic part that basically here the very first thing is we try to evaluate the value of the mid here i told you the two approaches and i am saying the second approach is the best one as comparable to the first i gave you the reason as well after that i talked about the logic where after evaluating the mid value we are just checking the three conditions is the value is equal to x is the value is less than the x is the value is greater than the x where x is the element that we're searching for now there are two ways to solve this particular problem either using recursion or without recursion even for every recursive code you have a iterative approach as well that's a very important thing to keep in your head so here when you are calling the same function again it means you're using the concept of recursion if you're just changing the parameters it means that you are doing a iterative approach here so that's the overall idea behind the binary search now i want to just talk about the logic in this particular video because i want to give you the time in the next video we will talk about the recurrence relation for the same i know until so far we have only only discussed that how we can solve any recurrence relation and i remember that at that point of time i told you that when the time comes i will also show you that how we can form up any recurrence relation as well and now i think in the next video the time came up so now we will try to understand that how basically we can form up any recurrence relation once i will be able to show you that how recurrence relation will be formed up once i will be able to show you that what is the recurrence relation for this binary search i am expecting you all to give me the final bigger time complexity which you all know we can do with the help of three methods substitution masters and recursive tree approach i hope that everyone remembers all those concepts pretty well because now in the upcoming videos there is a need of all those fundamentals which we have already covered up in our analysis module part right so so far we have discussed that what's the logic behind a binary search and we have seen that basically whenever we are talking about binary how this term came into picture because at each and every point in our logic we are either moving towards left of the array or towards the right of the array uh specifically taking the middle point or the middle index right depending upon what element we want to search now i think today is the right time to discuss about the recurrence relation of the binary search recurrence relation for the binary search now let's try to first of all recap what's the logic behind a binary search so we have seen that using recursion we can easily do the implementation for a binary search don't worry i'll try to give you the live implementation for the same in the next upcoming session but as of now we have seen that what we can do is that we are simply trying to basically doing three important major tasks here first of all we are trying to find out the middle value and the middle value is something which is i plus j minus i divided by 2 here the value of i is the starting index of an array that we have right the value of j is the ending index that we have in our average right now in this particular case middle value we can easily able to find out now what we are trying to do is that we are trying to simply using three conditions returning the value of the element that we are looking for suppose i am looking for an element x so recurrence relation for a binary search algorithm that we are trying to do it today right so here the very first thing which is that might happen that the value that we are looking for suppose this is the array name is r so the first condition can be the value of the error of mid might be equal equal to the element that we are looking for at that point of time simply we can return the value of the mid that we have another condition is it might be the case that the value is not equal and the value of the error of mid might be less than the value of x that we have means the element that we are looking for is somewhat greater than the value which is present at the r made if it is greater now we all know that we are using all these concepts in a sorted array so when we are talking about a sorted array at that point of time we are sure that we can move only towards the right side of the array because if the value that we are looking for is greater than the value of the r mid and the array is sorted it means that it should be present towards the right side of the army so basically we can call here the recursion what is the meaning of recursion calling the same function again for example initially our function name is binary search where we are passing the array we are passing the initial index i the ending index j and the value that we are looking for so here when we call the recursion what we are passing here is that we are saying that binary search and inside that i am passing again the value of r but now the initial index i know is not 0 here it should be towards the right side means it should be mid plus 1 afterwards we are having j and afterwards we are having x and the third condition can say that the value of the air mid that we are getting is somehow uh greater is comparable to the value of x that you are looking for means the element that you are looking for is somewhat lesser than the value present at armed and if that's the case again we need to apply the recursion here but now the value which needs to be changed is j not the value of i because i am sure that if this condition is satisfying the element should be present towards the left side of my sub array so here we can easily again apply a same function again by the name of a binary search and here we can say add here we can say value of i here we can say the value of mid minus 1 and here we can say the value of j with the help of which we will be easily able to get the clear-cut idea behind the uh recursive calls uh where we should go right and that's why it's called binary as well okay now we all know that either this condition will be satisfied or this condition will be satisfied or this condition will be satisfied it can't be the case that all the conditions are satisfying if we are talking about this condition this will be a constant time complexity part because here it's just one if condition and if that is satisfying we are simply returning the mid value now step by step i am approaching towards that how we can generate a recurrence relation so please pay attention towards here now here if this condition is satisfying so i have divided my complete array into a sub array in i have divided my completed into a sub array towards right side which contains almost half the elements of the original array so here i am calling the same function again with the half of the elements so here the recurs recursive or recurrence relation will be t of n by 2. here also if you will see so here y t of n by 2 because here we are approaching towards right side of mid right side of mid right which contains almost half elements and this is also i would say t of n by 2 but here we are approaching towards the left side of the mid here we are approaching towards the left side of the mid so either we can approach towards right side or we can approach towards left side but we can't approach on both the sides right we all know this thing right now it means that the recurrence relation will be equals to t of n now again i can say that when the value of n is equals to 1 it's a small problem then it's a constant based time complexity task or you can mention it as 1 also why because at that point of time you can only have to apply one if condition and according to that if condition you will be easily able to generate the result that whether that element is either equal or it will be not equal but the question is that when the value of n is greater than 1 what is the recurrence relation for a binary search that we have now according to the above logic that we understood here we can clearly say that the recurrence relation will be this one is again constant can i say c this one be either it will be t of n by 2 towards right side or it will be t of n by 2 towards left side so it will be t of n by 2 plus c and not 2 t n by 2 because here either t of n by 2 will belong to the left side of the sub array or it will belong towards the right side of the sub array these are the only two options that we have right okay now this is a recurrence relation that we have how many methods do we have to solve this recurrence relation i would say that we do have substitution method with the help of which we can solve this recurrence relation we do have masters theorem as well where the value of a is equals to 1 and the value of b is equals to 2 so the recurrence relation will be t of n which is equals to t of n by 2 plus c right here the value of a is 1 the value of b is 2. so log of a base b which is log of 1 base 2 is somewhere you can say is also constant right and the value of f of n is which you we used to represent as n to the power k log to the power p see here the value of k is also 0 here the value of the c is sorry p is also 0 that's why only we're getting the value as a constant so at that point of time because both of the so here the value that we are getting is also 0 log of 1 base 2 is 0 so can i say that the value of log of a base b is equal to the value of the k is equal to the value of the k and this lies under the case number 2 when they are both are equal at that point of time what we can directly do is that we can simply apply theta of c times whatever be the function that we have into log of n or this can be written as big o of or theta of log of n and yes this is the time complexity that we have uh in the binary search algorithm so this i have solved using a master's theorem that we have already discussed in our last classes i hope you all remember if you don't able to understand this part it means that you don't have watched the previous videos for the master's theorem so i would highly recommend at that point of time to go back and see those rules that we have discussed in the masters theorem apart from that the same thing you can do with the help of a substitution method as well so for example here you are having t of n by 2 plus c so what you can do is that you can substitute the value so you will be able to get n by 2 to the power 2 plus uh plus again it will be i would say c right plus above c will remain as it is so this is the first time we have the recurrence relation this is the second time we got the recurrence relation further if you will try to do it for the third time you will be able to get n by again 2 to the power 3 plus c plus c plus c because above c will remain as it is and this is the substitution for t of n by 2 to the power 2. this is the third time that you are doing the same task now again the question is that how many number of times do i repeat this task so it will be n by 2 to the power k which is equals to 1 because anyhow we want this term to be equals to 1 we want this term to be equals to 1 because we know that the value of t of 1 is somehow equals to 1 that is what we are pretty much sure right that is what we are pretty much sure so here this is what we know so can can i say that the value of n is equals to 2 to the power k and the value of k is equals to log of n base 2 it means that i need to repeat this task until log of n base 2 times okay so when i repeat this task until log of n base 2 times what i will be able to get is n by 2 to the power k plus c times k because here if you will see when you are doing three times uh third time you will get in you are getting 3c when you are doing two times you are getting 2c when you are having first time you are getting c it means that when you are doing k times when you are doing same step until k times where the value of k is log of n base 2 this is what the equation you will be able to get now you can place the value of k as log of n base 2 so it will be n divided by 2 to the power log of n base 2 plus c into log of n base 2 so here if you will see at each and every time what we're trying to do is that we are trying to substitute the recursive term that's why it's called as a substitution method that we already discussed it's just a revision of the previous concept that we already discussed and that's why i would i i was saying at that point of time that there is a need to discuss all those concepts prior because today i need all these things to be clear to you right now i think all these things whatever i'm writing is making sense to everyone why because we already have discussed in our analysis module that how we can solve any kind of a recurrence relation now here what we can do is that again n can be made prior and 2 we can take beside so it will become t in divided by n log of 2 base 2 so it will become 1 and this n and n will cancel out with each other so i will be able to get the value as 1 c times log of n base 2 so here t of 1 we already know is a constant value or 1 plus c times log of n base 2. so in other words we can say that the overall time complexity that we are able to get here is log of n base 2 and yes this is the time complexity that we are getting here right so either you are doing the thing with the help of a masters theorem or you are doing with the help of a substitution method the result will remain same and yes you can apply any of the method whatever it feels to you more suitable whatever it feels to you more easy you can do that that's why there is i i would told already to you all these three methods whatsoever approaches that we have in our algorithms analysis part right so this is the complete in-depth idea behind the recurrence relation of a binary search right so how first of all we uh got this recurrence relation that you should know so what is the approach with the help of which i suggest you that this is a kind of a recurrence relation for a binary search that we have that approach should be clear to everyone and afterwards the way we are solving the things either using a masters theorem or using a substitution method to get a final bigger time complexity is also should be pretty much clear to everyone i hope i am making sense to everyone with this i would like to in this particular session now i am expecting that everyone knows the logic behind the binary search everyone knows the in-depth intuition behind the recurrence relation of a binary search i think now it's the right time that i will move towards the implementation of a binary search so i will try to do the implementation in python of this binary search algorithm and afterwards i am pretty sure that you will be able to get a very much clear-cut idea about this algorithm which is pretty important for the interviews as well as i told you already right now i think it's the correct time that we will try to do the implementation for the same here i'm using a python programming language but it doesn't matter as i already used to talk a lot about this thing that you can use any kind of programming language it's just that the way the logic that i have explained to you that should be implemented right these are these are just the tools so for the implementation purpose i am using as of now the jupiter notebook so let me save the file first of all for you all so we can say that this is something which we can name it as a binary search implementation right now let's get started so what we can do is that let me try to first of all zoom the screen so that uh it will be pretty much visible to everyone so let me write the driver code first so what we can do is that we can take the array elements that we have suppose i want to take so whenever we want to do the implementation of binary search whenever we want to do the implementation of binary search the very first thing that we know is that we need to take the sorted array right so i will intentionally picked up a sorted array here okay so let's take 2 5 maybe 10 maybe 14 maybe 18 maybe 22 maybe 27 maybe 35 maybe i'm just taking some random numbers here right uh 59 okay i think this much is enough and suppose i want to search for an element having value maybe uh 40 okay so here the value of i which is the starting index that we have is zero okay and the value of j is something which is equals to whatever be the length of the array that we have minus 1 i know now everyone is aware about this as well because we already have a deep discussion about the functions in python related to line of air okay now what we can do is that i think it's the right time to do the function calling now so we can do a function call here here what we can do is that we can maybe store the result in a result variable and here i can call the function by the name of a binary search which is actually taking the complete array that we have which is taking the value of i which is taking the value of j and the value that we are looking for the element that we want to search for the position that we want so we can simply make a print statement afterwards that the searching uh element you can say the searching element is present is present at the index and here you can simply say the result right now let's talk about the function definition which is a very important task after writing the driver code now function will remain the same so the function name is binary search let me copy it i think that would be better complete parameters so here what we can do is that we can simply apply one while loop and we can say that until or unless the value is starting index is less than the ending index do these things for me what are those three things first of all we need to calculate the value of the mid which is nothing but i plus j minus i divided by 2. now what we can do is that i hope everyone have their logic in their head those three conditions what are those three conditions that we have if the value of the error of mid is equal equal to the value of the x that we are looking for you can simply return to me the value of the mid otherwise what you can do so in python we don't have else if instead of that while writing a syntax of the python programming language we are having alif that's the simple difference that we have so here if suppose the value of the error of mid is less than x means the element that i am looking for is present towards the right side of the mid at that point of time which parameter i need to change the value of i because now there is no need to start by default from 0. you can start from mid plus one so here what i can do is that first of all i am showing to you via a recursion so what is the meaning of recursion calling the same function again with different set of parameters with different set of parameters i can say right so that's what we are trying to do here correct now here if that is the case what we can do is that we will copy the function name so the function name is binary search and this we can simply return the same function name with the complete array that we have but now instead of passing i i am passing the value of mid plus 1 to j and it is taking the value as x else the last condition no need to write it automatically understand else case will be when the value of error of mid is greater than x so it can directly return to me the value as binary search and it is taking the value of r the value of i the value of mid minus 1 and the value of x that we are looking for i think this is pretty much fine if suppose all these conditions are not satisfying it means when it will go out of the while loop simply it will return to me the value as -1 because this minus 1 is indicating that the element searching element is not present in the array right if it is not present obviously how it will be able to show you the index number at that point of time we are saying just show to me the value as -1 here if we will run this code here we are passing the value as 40 and the output that i am getting is 8 let's try to verify this whether it's correct or not 0 1 2 3 4 5 6 7 8 it's pretty much correct if i will write suppose 20 which i am not able to see in my actual array if i will run this it is showing to me the value as -1 i hope it is making sense to everyone because as we have seen that after the while loop if it is not present if it is not verifying these three conditions it will finally go to the while loop and after completing the while loop it is returning to me minus 1 and that is actually what is happening here just one more test case suppose i am mentioning 10 here what will happen it is returning to me 2. it means that the code is running pretty much fine now this particular code is using recursion we did the implementation but without using recursion also we can do instead of calling this same function again what we can do is that we can simply change the parameters of i and j and that thing also will pretty uh will work pretty much fine how basically what i can do is that i will try to copy the same code which i have written down here and now what i can do is that so without using recursion how we can do the same code so let me take the same array same element that we are looking for i will remain same j will remain same and these things are pretty much same we are moving towards the function definition where we are finding out the middle value if we are able to find out the element that we are looking for we can simply return the value of mid otherwise we are going towards the lf part here instead of using recursion here instead of using recursion we will try to update the i parameter by saying that the value of i is should be equals to mid plus 1. similarly in the else part we can simply update the j parameter by saying that the value of the j is equals to mid minus 1 because that is what is required whether you are doing or calling a same function again or you are changing the parameter actual thing is happening same only right okay if i will do like this uh i think it's making sense let's try to understand here if you will see it is showing to me the same output that it has already showed to me in the above case but here i am not using any recursion meaning i am not calling the same function again if you will see inside this method definition or the function definition i am not calling anywhere the same function again with different set of parameters here if suppose i will mention again the 20 value let's see what will happen because this 20 is not present in the array it is clearly showing to me the value as -1 and that's what is expected in the binary search again what is the what is the recurrence relation it will remain same what is the time complexity it will remain same which is order of log of n so always remember binary search time complexity is something which is equals to order of log of n how we already have discussed that particular part now i think implementation wise everything is pretty much clear to everyone i have showed you both of the ways whatever way you want to apply you can apply it's just that the logic should be pretty much clear to everyone the way we are doing should be clear remaining implementation wise it's quite easy if you will be able to understand the logic behind the same this is what i used to say at each and every time in dsa it's just the logic it's just the problem solving skills that you should opt in the entire course also don't focus that how we can do the implementation what syntax we are applying because syntax keeps on changing depending upon the programming languages that we have but one thing is common that is the logic that you are applying to solve any kind of problem and i always say to my students that always try to develop a habit of building a logic instead of uh cramming something right so these things i hope are pretty much clear to everyone now i think it's the right time to discuss very interesting interview based problems which you can face whenever you're going for any good product based companies interviews uh specifically fun so i will try to discuss those problems which uh whose basic prerequisite is that you should have a complete depth knowledge of binary search which i have already listed in my videos i think i have took specifically simply for this algorithm also four or five videos why is that so because i know that it's very important topic it's the major uh i would say thing to understand even though it's easy but people used to do a lot of mistakes in these topics as well the only reason they are cramming the things the only reason they are just uh cramming that okay at this point of time i should go towards right at this point of time i should go towards left that's not an approach you should know why in every question you should know whatever you are doing why is that so right then only you will be called as a good programmer so i hope that the concepts are pretty much clear to everyone and everyone is enjoying the course with me so i'll see you all in my next video where now i will discuss about some interesting interview based questions while discussing those questions i have one simple humble request to everyone that whenever i will give you the question just pause the video think over the solution try to see that what is the approach that you will use suppose that question is given to you and then after that and pause the video and see the solution for that obviously i'll share the solutions for that i'll show you that what kind of approach should be the optimized approach but before seeing my approach or before seeing that this is the way this is the correct logic you should apply your logic you should apply you know your thinking process that what should be the way to approach this problem because now you already have a sense of what is binary search and how we can do the implementations for the same so i think this is enough for this video bye bye everyone see you soon in the next upcoming video where now we will talk about some interesting interview based problems for the binary search so let's get started please try to understand the problem statement first then please pause the video think over the solution and then unpause the video and see whether whatever approach you are applying is correct or not for sure this will help you to enhance your problem solving skill and that's what i used to advise to all the students whosoever is just starting their journey towards data structural algorithms okay the more you think about the problem statement about the problem solving thing the more you will be able to get an idea that how basically we should approach for any kind of a problem okay so please try to understand the problem statement now so first of all as i told you the major prerequisite to understand this problem is that you should have a good understanding of the concept of a binary search which everyone should know i am expecting every everyone is already aware about this concept now the question says that suppose you are having an array suppose you are having an array okay and inside that array you are having a list of numbers for example you have the values like uh maybe 20 maybe minus 30 yes there can be negative values as well 10 5 7 maybe 0 maybe you can say 29 okay and after that there are values which are infinite only after that all the values are infinite okay like this so this is a kind of an array which is given to you so what we are saying is that that there is an array which contains as of now n elements okay n elements it means the array index by default is starting here from 0 1 2 and we are moving and approaching towards the last element which is having n minus 1 index it's quite simple right now i know everyone is curious what's the problem statement we got an idea that okay one array is given to us and in that array some hypothetical infinite value i am saying is there okay now let's plate some further here 0 1 2 3 4 5 6 and 7. my question is that you need to calculate the index of a first infinite number what's the question again try to understand the problem statement is that try to give me the position or return me the position of first infinite element first infinite element this is the this is the question that which is given to you by the interviewer so he is providing some array in your technical interview and he is saying that in that array some hypothetical infinite is also there so at one point of time you are having the numeric values and afterwards you're not having any numeric data only infinite values are there so what's the position of first infinite for example here it will be 8 here it will be 9 here it will be 10 and so on but the output that your code should return or the logic that you will provide to me suppose if he's asking just for the logic part so what is the logic you will provide to me so that the output should be 7 because that is the index where the first infinite is coming inside the array think over it what will you do for example here it is zero so it can be negative number it can be zero it can be positive anything can be given to you but it's just that after some instant of time after having all the integers the next number towards that is infinite and afterwards once this infinite will come after that all the values are infinite all the values are infinite then again no i would say integer will come i hope that the problem statement is pretty much clear to everyone now just pause the video think over it that how can we optimize the code how can we reach to a solution where there is a lesser time and space complexity requirement i am expecting that you already post the video let's try to discuss it step by step the very first thing which i am expecting that everyone everyone is able to get an idea that that thing we can apply here is that you can say to me that one thing which you can do is try to do the linear search here what we can do here that we can maybe use a linear search where what we can do is that in linear search it will try to pick up every element step by step and it will make one simple condition that if the value present at r of i is equal equal to the value of infinite that we have at that point of time we can simply return the value of i otherwise loop will move on so here we can apply simply one for loop and inside that for loop we can apply just one condition it will again and again check that the value which is present at that particular index is infinite or not for example it's by default starts from 0 it will say that the value present at 0th index is 20. whether that 20 is equal to infinite no it will move ahead minus 30 no 10 no 5 no 7 no 0 no 29 no infinite yes that's what i am looking for so it will return the value as 7 here to me i think this approach is correct i think we will be able to get the correct response also the expected output also but what do you think is a time complexity here now i am expecting that everyone knows that how basically we can compute any time complexity here we can apply only single loop that is also running from the value of i equal to 0 to n minus 1 means until n number of elements that we have so can i say that here the approach that we are looking for is having a time complexity which is order of n and yes with the help of this approach i am uh clearly seeing that we can be able to get or reach to a solution that is expected but the question is can we optimize this can we reach to any other solution who is having a time complexity lesser than order of n what's about the space complexity before thinking that am i using any extra space no so as such there is a constant space complexity requirement but time complexity is order often so we need to think now specifically about the time complexity where i will be able to reach to a solution that where the time complexity is less than order of n do we have now another searching algorithm that we have is binary search now the question is can we apply somehow the approach of binary search here now the very first thing which maximum students will say no we can't apply if i'll ask you the question why is that so you directly say to me that you only said that whenever we are dealing with an array the very first preliminary condition to apply a binary search is that it should be a sorted array right now here i will say that your understanding is not apt it's partially apt you are seeing the array just physically but not logically that's what i will say to you what's the meaning of that physical logical array we are not able to understand right let's again try to think more clearly here right please pay attention towards this particular part because i have seen a lot of students who used to say a wrong answer here see here that when i used to say that array should be sorted while explaining the binary search i also told you that why i am saying this part because that sorted array is helping in my searching algorithm to decide that whether it should go towards left or right right now in this particular case when i am having a n elements size array in this particular case also am i able to decide that whether i should go towards left or right now think here please pose and think please see here if suppose i will be able to find out the middle value just like the way we used to do in our previous sessions which will be i plus j minus i divided by 2. once i will be able to get the middle value suppose i am getting the middle value as i am just hypothetic hypothetically taking this thing suppose i am getting the middle value as 5 okay now what i can say is that is the element which is present at this mid position is infinite or not suppose if it's not infinite can you clearly say that whether you should go towards left or right what i am saying is that that if suppose the element which is so here i'm just trying to write the logic just like the pseudocode so you can use any of the programming language your logic should be same right if the value of the r of mid that you are getting is equal equal to the infinite first of all let me talk about the not equal case if suppose it's not equal to infinite so can you say that whether you should go towards left or you should go towards right at that point of time think here i am pretty sure that what i told you in the problem statement that first of all all are integers and after that infinite will start and afterwards all the values are infinite so here we are very much sure that if suppose here the value is not infinite it means that the first infinite should always be present towards the right side of the array so it should always be present towards the right side of the mid it should always be present towards the right side of the mid right otherwise if suppose it is equal equal to infinite suppose you are getting the middle value and that mid value is something which is equals to which is equals to maybe this number suppose this number now here you can just check one thing if it is infinite so whether you should go towards left or right you just need to check one thing that what is the previous index number here if it's infinite it means that you have the idea you will be able to get an idea that you should go towards left side and explore towards the first infinite if not it means that this is the only force infinite index that you are having it means what i am saying is that that if suppose the value of the r of mid is somewhere is equal equals to infinite now there are two things which can happen one thing is that this might be the first infinite just like in this case here you can just check one if condition by applying that the previous index value is infinite or not if it's not infinite if the previous one is previous index element that you are having if it is supposed not equals to infinite not equals to infinite it means that this is the first infinite infinite infinite that you are getting at that point of time you can simply return the value of the mid because that's the index that you are having otherwise for sure if that value is infinite so you will explode towards the left side of the mid you should explore towards the left side of the mid i hope i am making sense to everyone right so here even though my array is not sorted here you can see that the error is not in a sorted fashion but still we can somehow apply the approach of binary search why because here in this question we can easily clearly set the path that whether we should go towards left right or we can directly return the value of the mid and these three conditions are only there when we are applying the binary search in our previous sessions as well right so here the only thing that you have to note here is that the important point to note now is that that always whenever you are looking for an array whenever you are looking for any kind of array always think that whether the array is logical or in other words i can say so in the note we can say that in an array we can logically apply binary search or not rather than just thinking about physical sorted array logically we can apply binary search or not means logically that can be having a clear distinction between the left side movement and right side movement very crucial point that you should think of left side movement and right side movement if logically you can move either the left side or the right side as clearly demonstrated in the binary search approach you can anywhere apply a binary search it's not just about physically errors should be sorted it's about logically also can we sort the array in such a way that we can clearly move towards the left side or the right side of the array and with the help of this example i hope everyone is able to understand what is the meaning of logically right here logically we can clearly distinguish that whether we should return the value of mid or whether whether we should go towards the right side or we should go towards the left side of the array that's what is the important statement which i want to state here and that's what it serves the purpose of the complete video i hope that everyone here is able to get the understanding in a broader sense about the binary search now and if in future someone is asking you such kind of problems before answering no directly by just seeing that okay the error is not sorted you should think over it and then answer it accordingly think that whether you can logically divide your array into two halves and divide the search space into two halves if yes then clearly you can apply binary search algorithm there it's just a modified version you need to modify some sort of coding but the thing will remain same the logic will remain same because here we can clearly divide our array into right and left part of our search space with this i hope that you will be able to get a better understanding of uh the binary search i hope we all know now that what is two-dimensional matrix or what is 2d array right where we have specific rows and the specific columns right so what this particular question is saying this question is you will you can see that this similar question is available in lead code platform as well so here what they want to say is that that we have been provided a 2d metric so user will provide some 2d matrix in that the two major points are there so 2d matrix will be of size m cross n where m is the number of rows where m is the number of rows that we have right and n is the number of columns here if you will try to see this this is nothing but 3 cross 4 so i can say that the value of m in our example is 3 and the value of n is equals to 4 correct now what the question says so here by default it will start from 0 0 1 2 0 1 2 and 3. now the question says two important points which i have already written on the blackboard here the first point says that the values which are given to you in a 2d matrix will be in a sorted fashion from left to right so here the sorting will be done from left to right so here if you will see all the elements in each and every row is in a sorted fashion one three five seven sorted ten eleven sixteen twenty sorted twenty three thirty thirty four 16 again sorted so here all the elements that we have in the matrix is in a sorted fashion this is the very first point the second important point is that if you will try to compare the first integer of every row so first integer of each row is having a value which is higher as comparable to the last integer of the previous row if you will compare the 7 and 10 10 value is higher as comparable to 7. again if you will compare 20 and 23 the value of 23 is higher than 20. so first point says row wise it will be in a sorted fashion every row whatever user will provide will be in a sorted form second point says that the first element present in each row will be having a higher value as comparable to the last integer which is present in the previous row which we can see in the example as well okay that's fine now i hope everyone wants me to speak up about the problem statement so problem statement says that given a target value suppose i am saying that the target is somewhere equals to three so my code will return either the value as true or false okay by saying that suppose if three is already present in the matrix which is given to us by the user 2d matrix so if 3 is present inside the 2d matrix so output should be true so in this example because 3 is present so output should return as true suppose i will type some random value the target value is something which is not available in my 2d matrix for example if i am writing 22 in that particular case it should return me the value as false it should return me the value as false so here if you will see what we want as a final result is a boolean value which is either true or false if the target is available in the 2d matrix which is a sorted manner in a row wise at that point of time it should return the value as true otherwise it should return the value as false that's the overall idea behind the given question which is given to us i hope i am making sense now what should be the approach that we should think of i think brute force approach is very simple uh which i think is everyone is able to understand what should be the brute force approach for this question any any any thing which you can think of brute force approach name approach also is the other word which i can say here means very first thing which is coming to your head like how we can solve this problem you will say to me that you can do one thing priya here you can start from the starting of the value and you will try to scan all the metrics step by step and you can just compare each and every element with the value which is you are comparing with for example your target is three so what you can do is that you will start from one you will just simply compare the value of one which is equal equal to three no i will move ahead it is equal i can return maybe if i am looking for a target value which is equals to 60 at that point of time what will happen is that it will again move ahead move ahead move ahead move ahead move ahead move ahead move ahead move ahead move ahead finally we got the answer finally the 60 is there so it will return to me the value as true at that point of time so what i want to tell you here is that that the brute force approach is that where we can scan all the elements that we have in a 2d array how many number of elements do we have it will be equals to m crossing right 3 cross 4 means in total we will be having a 12 elements so can i say that in a brute force approach when we are trying to scan all the elements step by step in a linear fashion the num the time complexity will be nothing but is equals to order of m cross n right because here we need to apply two for loops one for loop will take care of the rows for i equals to zero to m right for i equals to 0 to m minus 1 i would say and internally there will be another for loop which will start from 0 and will run until the number of columns and then it will try to pick up each and every element and we are trying to say that if the value of the r of i and the j is equal equal to the target value is equal equal to the target value we are saying just return maybe the value as true otherwise if suppose you completely scan all the for loop all the rows and columns simply you can return the value as false which indicates that there is no element whichever which you are looking for is present in your in your 2d matrix so this is a kind of approach where we are applying two for loops one will run until m number of times another will run until n times so for each and every value the value of j will start from 0 and will run until n minus 1 number of times so here overall in a brute force approach what we can see is that the time complexity will be order of m into n now the next question which i will ask from you is that instead of scanning each and every element just like the way i showed you where we are traversing 0 0 0 1 0 2 0 3 then 1 0 1 1 1 2 and 1 3 then 2 0 2 1 2 2 and 2 3 why are these two for loops are we able to do something which will be having a lesser time complexity as comparable to this order of m cross n can we do something here what do you think here if you will observe can we write this same 2d matrix in the form of a virtual array where consider that the indexes will be something so consider that there is a virtual array whose index will start from 0 1 2 3 4 5 6 7 8 9 10 and 11 means there is no original array that i am talking about i am talking about some consider that there is a one day array whose values will start from 0 and will end at 11 at that point of time if i will write the those numbers itself so here i was having the numbers in a row wise in a row major form i am trying to write it down and then because i know that the rows are in a sorted fashion and even the the last element which is present in each row is having somewhere a lesser value as comparable to the next row first element so if i will write the the complete matrix in such a way that just see this so here i am having the value as 0 1 2 3 4 5 6 7 8 9 10 and 11 so here index number will start from 0 it will be 0 1 2 3 4 5 6 7 8 9 10 and 11. so the elements that we have were 1 3 5 7 10 11 16 and 20 23 30 34 and 60. and the target value that we have is something which is equals to three [Music] so now if we have this kind of array where the target value is given to you how can you optimize your code you can easily apply binary search can i say you can easily apply a binary search in this kind of an array but here the question is that the array is not like this we have a 2d array but here i just make it down as a row major form that also i am saying is a virtual array it's not that originally in an extra space we are doing so then how basically we will be able to get what is the row number and what is the column number of each and every element that we have there is a formula for that now try to understand this part we all know how binary search will work so if we have this kind of an uh element so basically what we need to find out is the middle value now middle value will be 0 plus 11 minus 0 divided by 2 which is equals to 5 so this is something which is equals to mid here now i have to find out that for this particular mid index which is 5 what is the what is the actual location in my 2d array because that was the question which is given to me so here what is the number of columns that we have it is equals to 4 so always remember that you will be able to calculate the corresponding row for any element will be equals to whatever the index number that you are getting divided by the number of columns that you have so here it will be equals to 1. similarly you can be able to get the value of the column for that particular index that will be equals to 5 modulo 4 5 modulo the number of columns that you have so here it will be equals to again 1 it means it is saying to me that go to the row number one go to the row number one and go to the column number one you will be able to get 11 and that is so true when i'm moving towards row number one and the column number one i got the element as 11. now whatever operations i am doing is on the original 2d matrix but the way i am explaining to you is like something is happening on this virtual array here again what element i am looking for is 3 now i am looking for an element which is less than the mid value so i should go towards left or right i should go towards left it means that the value of my the value of my right as of now will become mid minus 1 right and the initial index left is equal to 0 in this particular case it means that now we need to traverse towards this whole area again i will try to find out the middle value now the middle value will come out to be 2 now the middle value will come out to be 2 because 0 plus 4 divided by 2 is something which is equals to 2 only now again the element what is the element corresponding to this two index what is the row number row number will be equals to 2 divided by 4 so it will be equals to what will be the value and what is the column number it will be 2 modulo 4. now here if you will go towards this 5 element here if you will see 0 and 2 and this is what you are getting here 2 divided by 4 is 0 2 modulo 4 is 2 and that is what you are getting here that is what you are getting the location of five it means that we will be able to extract any of the element by calculating the row number and the column number and we can apply the binary search approach on on this particular matrix as well so here we are optimizing our code from order of m into n to because binary search will take order of log of n and here we are dealing with the elements of m cross n so here you are reducing your time complexity from that sense from order of uh m cross into order of log of m into n again what will happen the target value is 3 still it is less than the value which you are looking for so again you will go towards the left side now again you will evaluate what is the mid value mid will be equals to 0 plus 1 divided by 2 again it will be equals to 0 plus 1 divided by 2 is 0 right we will take the lower bound of that so it will be 1. so now what will happen it will go towards right side only 3 is there so left is also 1 right is also 1 so middle will be 3 and target is also 3 so it will return the true value this is how basically we will be able to solve this problem so the in a nutshell what we are trying to do is that given a 2d matrix we are trying to generate a virtual 1d array whose index will start from 0 and will go until the element last element which is 11 so here what will be the last element so the left value is something left left value means the starting index will be 0 and the right value will be something right value means the ending index will be something which is equals to m into n minus 1 means in this particular case what is the value of m the value of m is 3 the value of n is 4 minus 1 which is equals to 11. that's why you can see that the last index that we are getting here in our question is 11 and how basically we will be able to calculate after getting a middle value what is the middle element what is the position of that we can easily calculate by calculating the row number and the column number i hope that i'm making sense to everyone this will be very much clear if you only know the concept of a binary search otherwise you will be in a trouble i'm against repeating this point now what i will do is that i'll try to do the implementation for the same and after doing the implementation i believe that everything will be pretty much clear to everyone so uh [Music] let me try to open my jupyter notebook so what i will try to do now is that so what i will try to do now is that i will try to just show you the implementation for the same so what i will try to do is that let me first of all save my file so this is nothing but we are trying to search in 2d array interview question okay now here if you will see let me write first of all the driver code here so what i will do is that i will take the metrics i will try to take the same metrics that we are discussing in our example so that everything will be making sense to everyone so we are having the elements 1 3 5 so let me take all those elements 5 and 7 the next value that we were having was 10 11 10 11 16 and 20 the next element that we have was 23 30 and 34 and 60. so this is a matrix that we have now what is the target value that i'm i'm expecting it is three okay now whatsoever be the result that we are getting we are creating a one function name so here what we can do is that we will try to make a function call so function calling will happen here so function calling will happen here now what i can do is that i can create one function here maybe binary uh search in 2d sorted metrics it will be too long binary search in a sorted matrix i want to give some meaningful name or let me try to give it search in a sorted matrix okay so here what i will do is that i will pass the metrics and i will pass the target value now whatever be the result we are getting we will print that so either we should get true or we should get false now here what i will do is that i will provide the function definition can i say right now here what we can do is that we can just copy this thing and we can say diff the function name and now what we can do is that first of all we need to calculate what is the value of number of rows so it is nothing but len of the matrix that we have this is nothing but the number of rows that we have we can make one base condition that if the number of rows itself will be equal to 0 it means that there is no element which is present inside the matrix we can simply return false because whatever value you are looking for if there is no rows in a 2d matrix then it doesn't make any sense right now if that condition is not satisfying at that point of time what we will try to do is that we will try to first of all evaluate the number of columns so here we got the value of the number of rows now how we can calculate the number of columns in the python programming language it's very simple number number of columns so what we can do here is that we can say len of matrix 0 that's it right now once we will be able to get the number of columns what we can do is that just like the implementation of binary search which i showed you i hope everyone remembers so we need to define the uh starting index maybe you can say left and right ending index right side right it will be zero and it will be the right will be m into n minus 1 as i already explained in in the blackboard part now what we can do is that we can make one while loop which is left less than equals to right what we can say is that first of all we will evaluate what is the mid value mid value will be equals to left plus right minus left by 2 all these things we have discussed why we are doing finding out the middle value like this i have already discussed now what we get we will be able to get the mid index with the help of this i want the mid element how will be able to get the mid element mid element will be equals to the matrix of what is the row number how we can get the row mid divided by n number of columns how we get the column mid modulo n we will be able to get the column now we what we need to do is that we need to check if the target is equal equal to the mid underscore element then we can simply return the value as true we can simply return the value as true if suppose the target in life what we can type as a condition now suppose the target that we are looking for is having a smaller value as comparable to mid element now at this point of time whether i should go towards left or right when the target value is lesser than the middle element i should go towards left when i will go towards left i will update the value of my right i will update the value of my right which is equals to mid minus 1 correct in else part we can update the value of left as mid plus 1 now suppose if we will exit out of the while loop still will will not able to get any true statement it means it will automatically return the value as false which indicates that okay the values that you are looking for is not at all present inside your 2d matrix right let's try to run this code we'll try to see what we are getting so it is resulting as true now what i will do is that just to see the test cases what we can do suppose i will write the number as maybe 33 which is not present let's see so it is returning the value as false suppose we will write something like maybe 11 11 is there 12 again false if we type 11 it's true so basically if you will see from this part we are doing only binary search implementation we are doing only binary search implementation that we already did in our last sessions last video i have created one separate video for a binary search implementation part i remember very well i hope everyone remembers this post this part so if you will try to see the coding portion of binary search implementation and what i did here is exactly same what's the difference is how you are extracting how you are extracting the elements from the 2d array right so basically the row number we are calculating by taking the number of uh by taking whatever index you are calculating divided by the value of n where n is the number of columns that we have and column number is straightforward equals to whatever with the index that you are getting modulo modulo will give you the remainder and that is the only knowledge which is required to implement this question if someone knows that how we can extract the row number and the column number from a 2d matrix in order to extract any element then he or she will definitely give the result within a second this is a medium level problem but i think that after listening this explanation pretty well you will be able to do this particular question within seconds it will not take much time to implement the things if you know what is binary search if you know what is 2d matrix if you know how we can extract any element from the 2d matrix then it's quite easy problem i would say right i hope that everything whatsoever we have covered up so far will make sense to everyone if you still have any sort of doubt i will for sure share all the materials whether it be the implementation code or whether it be the the conceptual part which i have discussed in in this particular class but if you still have any sort of doubt do let me know i'll try to resolve it as soon as possible with this happy learning tool i'll see you all in my next video where now we will discuss about another searching algorithm called as turner research that's also amazing again the major prerequisite to understand that part also is that you should have understanding of binary search that's why i used to say that binary search is quite important algorithm right whenever we are talking about a ternary search it clearly indicates that now we are having three different paths the understanding is completely the same that we already have discussed in our binary search part means that this particular searching algorithm is also applicable only when you are having a sorted array the very first important thing again the same thing which i am talking about in binary search as well is that that whenever we are having a sorted array at that point of time this ternary search is pretty useful okay what will happen and how it is different from the binary search that we have covered up in our previous part for example here i am having an array which is 1 2 3 4 5 6 7 8 9 and 10. so the index number of an array will be 0 1 2 3 4 5 6 7 8 and 9. now here if you will try to see this is the array that i have now in binary search we are calculating the middle value how by saying that the value of the mid will be equals to l plus r minus l divided by 2 y two because here in the binary search we want to split our array into two halves but when i am talking about ternary search i want to split my array into three halves i want to split my search space into three halves so here what will happen is that you will find out two middle values one is something which i will say as the mid one mid one which will be equals to l plus l is the left side extreme r is the right side extreme so it will be l plus r minus l divided by three this is the first thing that we have evaluated and the middle two is something which is equals to r minus r minus l divided by 3. in this way you will be able to split your array into three equal halves right for example in this example if you will see the value of l which is the left index is 0 the right index is 9 right now here what we can do is that the value of the mid 1 if i will just put the values it will be 0 plus 9 minus 0 divided by 3 which is equals to 3 and the value of mid 2 will be equals to 9 minus 9 minus 0 is something again 9 divided by 3 so it will be 9 minus 3 which is equals to 6. i hope i'm making a correct calculation so here if you will try to observe this is the value of the mid one and this is the at the index number six so here mid one is having the index number three so let me go to index number three so this is the index number three mid one midi 2 is something which is having an index 6 this is something which is equals to mid 2 right so in a way we will be able to get the values which is equals to mid 1 and mid 2 right now what is your next task here if you will see this is your first part of your array first subpart of your array this is your second subpart of your array and this is your third sub part of your array so this is the first part this is your second part and this is your third part meaning in the ternary search what you did mainly is that you divided the search space into three different parts that is the important thing here to understand now the same thing will happen the very first check that you will do for example for example that the element that you are looking for is equals to maybe 5 okay so first of all you will check that whether the element the element that you are looking for which is x is equal equal to the value of r of mid 1 so is the value of error of mid 1 is equals to x that you are looking for so this is the searching element that we are looking for right now we are just checking that the element that we are looking for is equal equals to the value present at mid 1 if you will see it's not true because the value present at r of 3 is 4 so this condition will not satisfy if it is if it will be satisfying then obviously we can simply return the mid one index otherwise in the second scenario what we can do is that r of mid 2 is either equal equal to x so now it will again go to r of 6 which is equals to 7 the value is not equal to the element that we are looking for if it is equal at that point of time you can simply return the value as mid 2. so these two conditions are simple base conditions that is pretty much clear apart from that now another thing if suppose the element that you are looking for is supposed less than the value present at air of mid 1 if that is the case the element that you are looking for for example here the element that you are looking for is not 5 but is equals to maybe 2. in this case in this case so let me write it below what i am saying is that the element that you are looking for is equals to 2. as you know that the array is sorted and the element that you are looking for so what is the value present at r of mid 1 the value is equals to i think 4 right because error of 3 is 4. now you know that the element that you are looking for is somehow lesser than the element which is present at r of mid 1 then where should you go you should go towards first part second part of the third part i have already already described what is first what is second what is third so we are pretty sure that at that point of time i should go towards the first sub part of my array means at that point of time you need to just update the value of the j value which is the last index as the mid minus one right because you want to reduce your search space until that uh you know or r value which is the extreme value until that first sub half means you want to go until you want to look for until this part this portion of your array because you know that the element that you're looking for is lesser than the element which is present at this location of r of mid one okay if suppose the element is somehow greater than the value present at r of mid two at that point of time what will you do so what i'm saying is that that suppose you're looking for an value which is equals to maybe nine which is equals to maybe nine so what in this particular scenario if you will look into this what is the value of error of mid 2 here if you will see the value of error of mid 2 is in this case is 7 so now you are sure the value of 9 which i am looking for is greater than the value of 7 right so at that point of time i know that the value will be present in my third subpart so here there is a surety that your value will present in the first search space i can mention like this and this condition will give you a guarantee that your value of l will be equals to mid 2 plus 1 here it should be mid 1 minus 1 because now here we are having two mid one and mid two it means that it is giving us a surety that you should go towards the third search space and if suppose if suppose this condition is not satisfying means we are not moving towards first search space if suppose this condition is not satisfying means we are not moving towards third earth space which one is left only the second third space at that point of time there is only one condition which is left where you need to update both the values that is you need to go to mid 1 plus 1 until the value of mid 2 minus 1 so this is the location of a second search space so here i am just writing the sudo code don't go with the syntax we will do the implementation in our next part but here the only thing that you need to understand is that that how we can approach towards first subpart second subpart and the third subpart and i hope that i'm making sense to everyone that how basically we can approach towards the first sub part of an array seconds are part of an array and thirds are part of an array this is what i want to convey in this particular session where i have picked up all the different kinds of examples to just demonstrate you that how basically you can choose the value of first second and third sub part of the search space and how this ternary search is somewhere different from the binary search in the next particular part i'll try to show you the recurrence relation for the same i hope that maximum students will be able to get an idea what should be the recurrence relation but still i'll show you that and then we will try to do the implementation for the same as well very simple i know but still many people usually get confused so those who have a good understanding of binary search i think they will find it pretty easy instead of just dividing it by two we are dividing it by three we are finding two middle values we are dividing dividing our array into three search space that's the only difference and according to that conditions will vary okay so so far we have discussed that in a ternary search the major approach is to divide the search space into three halves and then we are looking for that whichever element that we are looking for is either lying in the first part or the second part or the third part considering those things in our mind now could you tell me that what should be the recurrence relation for this ternary search so what is the recurrence relation for this ternary search now when we talk about this recurrence relation obviously we are not forcing or we are not saying to the code to go in all the three directions it will either move towards the first subpart or it will move towards the second sub part or it will move towards the third sub part it means that the recurrence relation is equals to t of n which is equals to t of n by 3 because we are dividing our search space into three halves plus c where c is the constant which will take a constant time to just take just checking the if conditions right and returning the same so majorly this is the recurrence relation for a ternary search now you can solve this recurrence relation with the help of various methods for example if i will try to show you show you using the substitution method so what will happen so you know that when the value of n is small for example if your search space is containing only the single element at that point of time can i say that it will take only the constant amount of effort but when the value of n is greater than 1 at that point of time this is the recurrence relation that we are getting t of n by 3 plus c by saying that when the value of n is equals to 1 it means that there is only single element present in an array and at that point of time we can just move a simple if condition that the element that a user is looking for is present in the array or not that's it so now here what we can do is that we will try to substitute this value of t of n by 3 so if we will substitute it will be equals to t of n which is equals to t of n by 3 to the power 2 because we will again further divide it by 3 plus c and above c will remain as it is right if you will do it further for the third time again it will happen it will be t of n by 3 to the power 3 plus 3 times c 1 c is for this substitution part and 2 c's we are copying from here so it means that if you will try to observe here that we are in each and every step while going below dividing the value by 3 by 3 by 3 by 3. now the question comes that until what point of time we keep on repeating this task so can i say that it will be n by 3 to the power k and this value should be equals to 1 because what we want is that we want this value to be equals to 1 so what when when this will happen so you you can just solve this equation it will be n by 3 to the power k which is equals to 1 n is equals to 3 to the power k so the value of k is equals to log of n base 3 this is the value of k that you are getting it means that you need to repeat this step until k times and when you repeat this step until k times you will be able to get the value of t of n which is equals to t of 1 plus can i say it will be equals to c times log of n base 3 or direct i will not jump directly towards this step let me show you so if it if we will repeat this until k times it will be t of n by 3 to the power k plus c times k how is that so because here if you will see first time this is the equation second time it will be power 2 and 2 times c third type power 3 3 times c if i am saying i am repeating this as a same task k times so power k k times c now you can place this value of ks log of n base 3 so what i can say is that t of n by 3 to the power log of n base 3 plus c times log of n base 3. now here what you can do is that you can take the value of ns up front so what will happen is that it will be t of n by n to the power log of 3 base 3 plus c times log of n base 3 now here this will be equals to 1 this will be 1 and t of 1 is nothing but is a constant plus c times log of n base 3 so the overall time complexity that you are getting here is log of n base 3 right so this is the overall time complexity of a ternary search so here we are specifically interested and we are talking about a ternary search only right so this is the overall idea behind the recurrence relation followed by the time complexity of a ternary search now there is one question for you all i'll not give the answer for that i'm looking for your responses the question is very simple we have understood what is binary search we have understood what is ternary search you all know now what is the time complexity requirement for the binary search and for the term research as well specifically saying order of log of n base 2 will be for the binary search order of log of n base 3 will be for the ternary search can you give me one simple explanation that which particular searching algorithm is the best one according to you and why is that so don't write or don't say some random answers uh justification for that is pretty much important so simple straightforward question says that if suppose array is given to you array is sorted also what do you think whether we should divide our search space into two halves or into three halves and here we are studying about ternary we can have four half cells as well depending upon the requirement what do you think should be the better way should we go towards binary or should we go towards ternary because these two things we have understood so far right in the next part of the video you will see the implementation of this ternary search it's quite simple because if you will know the concept implementation is very easy this is what i used to say at each and every time but still i'll try to show you now let's get started with the implementation of ternary search very simple it's just you have to just be very much conscious in the session you will be able to get the understanding ternary search okay here what i can do is that first of all let me write the driver code here where i can pass the array which is equals to 1 2 i'm taking a sorted array as we have already already discussed that the premise condition whenever we are implementing binary search or a ternary search is that array should be logically sorted what's the meaning of logically sorted already conveyed in my past sessions do remember i hope everyone knows that concept now what i can do is that i will say that the value of the starting index which i am representing as a left index will be zero the value of the right index which i am representing by r is equals to what is the length of the array that i have minus 1 right and now what i can do is that uh i can mention which element i want to search for for for example i'm looking for an element 2 okay so i i want to search for the element 2 means at what particular index this element is present now the result is this so here what we can do is that we can do a simple function calling now function calling so here what i can do is that i will create one function by the name of a ternary search now this function will take the value of l this will take the value of r this function will take the value of x the element that we want to search for and the complete array now we can print the result which says that searching element is present at index and here you can say a comma you can mention the result right you can mention the result here i hope that i'm making sense to everyone uh right now the only thing where we need to do is the function definition right so now what i can do is that i can just copy the function name or we can copy the parameters as well here what we can do is that we can simply say while the value of l is less than equals to r i want this loop to run internally first of all we need to calculate what is mid 1 it is nothing but l plus r minus l divided by 3 mid 2 which is nothing but is equals to r minus r minus l divided by 3 right once we will be able to understand the concepts things will become very easy right automatically we will be able to do all stuffs we will be able to play with the code as well so now what we can do is that one simple thing if suppose the value of r of mid 1 right if suppose the element that i am looking for is equal equal to this value in that case what i can do is that i can simply return the value of mid 1 otherwise if suppose the element that i am looking for is equal equals to r of mid 2 in that case simply return to me the value of mid 2 if suppose the element that i am looking for is less than the value present at r of mid 1 i am sure that it will be present at the first part of my array so what i can do is that i can simply call the function again this is also known as recursion so what i can do is that i can return ternary search where i can say the value of l will remain same the value of r will be mid 1 minus 1 x will remain same and r as a complete array will remain same if suppose the element that i am looking for is somehow bigger as comparable to the value which is present at r of mid 2 it means that this is the point where my array element belongs to third sub part of my array so what i can do is that i can say i can simply call the same function again ternary search but now my starting index will be from mid 2 plus 1 because that's belongs to third sub part of my array are x and the r right otherwise if suppose it is not belonging to the first subpart of my array it is not belonging to the third source space as well automatically what it indicates that it belongs to the second subspace so again we can call the function but now the value will become mid 1 plus 1 until mid 2 -1 x and r now if suppose we are done with the complete while loop but still i will not able to get any uh index it means that we can return that as -1 which simply indicates that the element that you're looking for is not at all present in your array let me try to run it here it is showing the value as one if you will see we are passing the element as 2 which is at present is index number 1 right it means it is showing the correct thing for example if i will change this value of x as maybe 8 let me see yes it's showing it correctly it is present at 7th index suppose i am mentioning 20 it if you will see now it is showing to me minus 1 it indicates that the element that you are looking for is not at all present in your array right so here if you will see one simple thing one simple thing that you need to understand that how this particular condition will go towards the first search space in a ternary search how this particular condition will reach towards the third search space in an array and how the last condition automatically will go towards the second search space in an array if you will be able to understand here we are dividing our search space into three major halves either it will go towards first or it will go towards second or it will go towards third according to that our array will be able to our code will be able to detect that which particular location element is located and it will be able to generate the results here if you will see we are using recursion meaning we are calling same function again but with different set of parameters can you use can you do the same thing without using recursion why not now uh do one thing uh same code everything will remain same instead of using recursion you just need to change the values for example here you can change the value of r as mid 1 minus 1. try to do it on your own and do let me know whether you will be able to get the same results or not so this is the overall implementation of the ternary search that i have showed you in today's part right so this is the overall implementation of ternary search very important but many people or many students are not aware about this just simple fact we are dividing our search space into three halves that's the only uh funda in this particular case so when you will talk about the recurrence relation it is also very simple because we are not going into all these three search spaces we are going among out of these three only one so that's why it will be as we have discussed equals to t of n by 3 plus the constant c right so yeah this is all about the implementation of ternary search i think we have covered up in a lot of depth if you still have any sort of doubt do let me know i'll for sure try to resolve it as soon as possible with this happy learning tool bye bye everyone see you soon soon in my next upcoming video