Learn the Concept of Searching Algorithm

1. Introduction: Hello guys, welcome back to my new class. I am Martin, I'm a YouTuber programmer and a lot more. I like teaching people on the subjects in which I have a good knowledge. In this class, you are going to learn, implement, and use different data structures concepts, and learn various popular programs and data structures and algorithms. From scratch. I have taught all the concepts from the scratch in a simple and understandable way. Anybody can understand it even if you are a new tool, DSA. Even if you are new to DSA, you will be able to develop your analytical skills on data structures and use them efficiently. This glass, initially you will be able to learn a board video searching and sorting algorithms. With time, I will be adding more than more quality content and I will be teaching more number of concepts, data structures, and algorithms. If you are looking for someone to guide you while solving DSA problems, then this class is for you. We will be solving quality coding problems from the best websites which were asked in interviews. If you know the basic understanding of one programming language which has, oops, linear, then this class is for you. This class is designed for complete beginners and intermediate and for those who are looking to solve some quality coding problems in later structures and algorithms. This class is not designed for the last day interview preparation. You may be new to their data structures. You have already studied and implemented data structures. Bird still, you feel you need to learn more about data structures in details so that it helps you to solve challenging problems and user data structured efficiently. In this class, I have taught how to sort on conceptual problems from the scratch, which you can understand easily and you can solve some more problems for the fun. I will be giving you the list of websites which you can use to practice for your coding preparation. If you are thinking about to start BSA, then I highly recommend to watch this class as it is easy to learn. And I have explained in broader way with examples at each and every step. And after solving conceptual problems, you can easily understand and solve any type of problems on that concept. If you know the concept already before, you can skip the concept videos and watch from the coating solution videos. You guys to not skip any class videos because if you skip one class video, you will get confused at the end. Have created this class in such a way there it is interconnected to previous class videos. I hope you understand it. So thank you so much for getting the class. I can't wait to talk to you. I will go ahead and see you guys in the class videos. 2. Understanding Linear Search Concept: In this video, let's discuss the linear search. Linear search and basically that you are given an array, a number. You have to find the number in the array. We have to find the whether the number is in the array, are present in the array or not. If the number is present, I need to know its address. I need to know each location index. I should say. If the number is not present, then answer will be minus one. There is no valid index for that number. Now, let's take an example and understand. Say I have an odd it like this. 01234, fight with values 81159. Suppose these are the values. I have a number. C number is 15. Know, I need to find out whether 15 exist in an array or not. That I saw 15 years presenting the array. I need to find out your surges. In this case the address, I mean, it's index. In this case the index is four. So if we are to find though that if index is 15 present, now, we have to think that how should we actually do it? See you have to search for 15, right? So the basic approach to do this will be, I will result every element of the array. Check whether the element at a particular index is 15 or not. I will do it for the other indices of this array, deal. I'll find 15 till I'm sure that 15 does not exist in the array. What do I mean by that? Is, these are the indices. These are the elements are the index. Visit index 0. Check if 15 is there or not. So 15 is not there. Then I will move to the next index of the audit, which is 15, is present at index one or not. I will move to the second index of the array. 15 is known. The third index of the array 15 is not there. For the index of the array S, I find 151515 is there. That means at this point I can see 15 exists at index four. What is my answer? Which I obviously have to read them. I will quit. Now, there is no need to check elements are indices after that. The first dark currents are 15. Easy enough for me. That's it. I know instruct. This is the scenario. Now let's take an example of a number does not exist in the array. Let's say the number is 20. The process 40120, nor there for two twenty three twenty is nor there for no final. I'm there actually. You have visited all the valid indices of the array iron. You could find that number. That means after I have searched all the demand side that all indices i and I could not find any. I can conclude there does not exist and it is scarce. Minus one will be my answer. These other two possible scenarios and other, another example plausible scenario can be, let's say the array like this, 5101515, the multiple occurrences of 15. And I am searching for 15. Then what should we be? The my answer, I know 15 occurs at index two as well. An index for us with our answer should be two or four. In this case, answer will be first index at which we find 15. It is still from the beginning. So we will start from the beginning and the first index that we find it. I hope an idea is clear. So all you have to do is travel to the every element. Now in order to travel, you should just take a variable I started from 0 in the last index. The size of the array is then, should I do n minus one? Check it every element, whether the IT element of the array is equal to the number that I'm searching or not. This is the rough idea. As soon as I find a number, I can stop my and-a-half my answer. I didn't guess I saw just in case I've exhausted all the elements, searched all the elements. I could not find out the umbo then I can say that does not exist in the array. This is the basic approach around it. I hope this approach is clear. You can try and code it yourself. 3. Linear Search Problem Statement: Hi. In this video, let's understand the problem statement of linear search. You have been given and random integer array of size n and an integer x. You need to search for the integer x in a given array. Using the linear said. You have been required to return the index at which x is present in the array. If X has multiple occurrences in the array, then you need to return the index at which the first occurrence of x be in control. In guess x is not present in the array. Then written minus one. Linear search is a method for finding an element within the array. Sequentially checks each element of the array until a match is found, auto the whole array has been searched. The input format is the first line contains an integer d, which denotes the number of test cases or grid is to be done. Then if this goes follows, guys don't worry about this line, will see this afterwards. The next, the first line of each test case or grading contents and integer n representing the size of the array. So what they're basically telling is the first slide here. This first line. The first term of each test case or query containing an integer N represents the size of the array. So this seven here is a size of this array. Second, again, Glenn content CAN single-spaced interpreted integers representing the elements in the array, or at least these lines is in this. These are these lengthy seven. The size of this array seven. This represents the elements in the array separated by this base. Next line, the third line contains the value x odd integer to be searched in the given array or the list. This line is the key or the key. The number we need to search, whether it is present in the given array or at least the output format that expanding from each desk goes bring the index at which x is presented. We have to print a which index that element. It could be so certain. X in this case is present or not. If it is not present, then return minus one. Output for each test case will be printed in a separator line. Whatever the test guess, whatever the element we need to search should be printed in the new line. The constraint, they argue ins, the size of the n should be within this range. Or the element to be searched true should not cross the integer capacity. That is, minimum capacity, that is minus 2.31. And maximum capacity of the integer is two to the power 31 minus 100. Time limit should be within 1. Second order would of course be whatever the core we are writing should execute within the time limit of 1 second. And this is the sample input. This is the first best-case. First input or first test case. And seven represents the size of the array. And this is the elements of the array of size n. The first element is 213 forty one, thirty six, twenty eight element. The three represents the element to be searched in the array. In this case, x equals to three. In the output they're expecting from us, we should return the index at which three is present or x is presented. For the first three is present, or the index for the output is four. As you can see, the size of the array seven. This first one is 0 index first index, second index. The order next entry is for the index. So we should written for output. The next sample input two, the size of the array seven. And these are the elements of the array. And we need to search nine. X equals to nine. As you can see, the size is seven and we're not able to see any nine in this array. So we should return minus one. They're expecting us from a studio, minus one in the first case. And the second input is size of the array is five. And the elements of the array are 7895. Key, or the limit we need to sort it in the array of size five is five key element to be searched this file in the array of size 53785905. As you can see, the five is appearing two times in the array. As you can see, the five is two times in this array. So we need to return the first documents or file. That is the index at which the first time the fiber goods there is an index two. So they're expecting us to return. I think you guys have understood war. The cushion is lead score. 4. Linear Search Algorithm Video Solution: So now we have to think about the core for linear search. I will quickly write down the array. Let's say this is the array that I'm searching for. And we have to find out the value that we're looking for is 15. Then how will we actually proceed with the writing code? We have a function, return type of the function will be integer. Let's see. The index linear search. Let's say is the name of the function. We will be given the added in vitro, we have to search. Let's say input is the array. We will be given the value that we have to search for. If you are writing the coordinate C plus plus size will be given. But if you're writing code in Java, you can easily find out the size of the input dot blend. This case of the size, I'm assuming n is the size. Input is the area that I have to sort to do, and the value is the number that I'm searching for. No, What should we do? Starting from index 0 till index set, I have to search at every index. That means I will need a loop. Starting from index 0. The last index, last index is n minus one. I'm assuming N as the size of the edit I plus plus. So this loop will just result each and every element of the array. All I have to do is to this. So this should be input. All have to do is I have to check whether the ICT element know all we like it ICT element of the array. Writing this input on port, I will do me the item. And now all I have to do is compare whether this element is equal to the element that I'm searching for. Double equals becomes weird competing. If this is equal to the value that I'm searching for, that means I founded and that's it. I don't have to proceed further. My answer, I can simply return the index. Now the index here is i. We don't have to return the value of the number. We have to return the index at which the number is present. In this case, the indexes i. If the current number is not equal to the number that we are searching, then shall I return minus one here? That I cannot find the number in the array? No. I think this is a major mistake. So be carefully deck, we don't know this mistake. See, all we're doing is we're just comparing the current element when we're searching. If this is a match, then I'm definitely show that the number is present in the array. But if this is not a match, then that cannot say that the element is not present in the array until and unless I've searched all the elements in the array, conformation that I limit does not exist. I can get that only after I've searched all the elements. So if I haven't, this is just, this is just a local literature. I've just compared with the limit. I cannot conclude that if it is not present in the array, writing LCA or understanding minus one year is actually incorrect. Then what do we have to do is in L Spark. And Spark simply means that the current element is not the one that you are searching for. All you have to do is move to the next, telling me if there is an extra element in the array. That means in ideal case, we have to do I plus plus in which we are anyway, he's doing it because this is FOR loop. So as we'll simply do this, I can see that the limit does not exist in the array. Only after this for loop is exhausted. Only after this for loop is complete. We did not find the element. Because hard the element when did we would have returned one? We would have written. If the for-loop is complete and you are reaching our disposition there, it means you do not find the element and you should return minus one. Element wasn't there. I will return minus one only when I'm completely sure that I've searched all the elements and it is not that. Right. So I hope you are clear now. I hope you are clear with the statement is put where and what is the reason that we're running? And running and running minus one here. What are the possibilities that we could think a board? So I hope this use your clarity and you're clear with it. Thank you. 5. Linear Search Coding Video Solution: Hi. In this video, let's understand the problem statement of linear search. You have been given and random integer array of size n and an integer x. You need to search for the integer x in a given array. Using the linear said. You have been required to return the index at which x is present in the array. If X has multiple occurrences in the array, then you need to return the index at which the first occurrence of x be in control. Guess x is not present in the array. Then written minus one. Linear search is a method for finding an element within the array. Sequentially checks each element of the array until a match is found, auto the whole array has been searched. The input format is the first line contains these are d, which denotes the number of test cases or gray distributed. Didn't have discuss follows. Guys don't worry about this line, will see this afterwards. The next, the first line of each test case or query contents and integer n representing the size of the array. So what they're basically telling is the first line here, this first line, the first line of each test case or query containing an integer N represents the size of the array. So this seven here is a size of this array. Second, second Glenn content CAN single-spaced separated integers representing the elements in the array or list. These lines is in this. These are these lengthy seven. The size of this array seven. This represents the elements in the array separated by this base. Next line, the third line contains the value x, or in teaser to be searched in the given array or the list. This line is the key or the key. The number we need to search, whether it is present in the given array or at least the output format that expanding from each desk guess bring the index at which x is presented. We have to print a which index that element. It would be so certain x in this case is present or not. If it is not present, then return minus one. Output for each test case will be printed in a separate third line. Whatever the test case, whatever the element we need to search should be printed in the new line. The constraint is that the size of the n should be within this range. Or the lumen to be searched through should not cross the integer capacity. There it is. Minimum capacity that is minus 2.31. Maximum capacity of the integer is two to the power 31 minus one. The time limit should be within 1 second. What are the core? The core we are writing should execute within the time limit of 1 second. And this is the sample input. This is the first test goes. First input or first discuss. And seven represents the size of the array. This is the elements of the array of size in. The first element is 213, forty one, thirty six, twenty eight. So the element, the three represents the element to be searched in the array. In this case, x equals to three. And the output they're expecting from us is, we should return the index at which three is present or x is presented. For the first three is present, or the index for the output is four. As you can see, the size of the array seven. And this first one is 0 index first index, second index. The order next entry is for the index. So we should return for it. The next sample input to the size of the array seven. These are the elements of the array. And we need to search nine. X equals to nine. As you can see, the size is seven and we're not able to see any nine in this array. So we should return minus one. They're expecting us from a studio, then minus one. In the first case, the second input is size of the array is five, and the elements of the array are 7895. And the key or the limit we need to sort it in the array of size five is five the key element to be searched this file in the array of size 53785905. As you can see, the five is appearing two times in the array. As you can see, the five is two times in this array. So we need to return the first doctrines of frame. There it is, the index at which the first time the favorite goods, there is an index two. So they're expecting us to written. I think you guys have on let's reward. The cushion is so let's call, Hi. I hope you have quartered on your own. After watching my linear search algorithm video solution. If you haven't, I highly recommend you to take a pen and paper. I think a board, the solution. You will feel it amazing if you solve it on your own. Please don't Google the solution. You will not learn anything if you just copy and paste. I once again, highly recommend you to pause the video and solve it on your own and come back to watch the coding solution review. I hope you got the solution by now. If you have got stuck in between, it's totally fine. Just gone one in the beginning. And it happens. If you practice more number of problems, then you can get a good grip in solving any kind of problems. Back to the video solution. Now, this window you are watching is called Online Code Studio. I found this platform Amazing. So I will be solving all the problems in the future from this website. You can go to the website and practice some more problems after this video. So basically here we just have to write the logic. I mean, we don't have to write the main function. Everything is done inside the core studio. We just have to write the logic and submit the code. Will run the other test cases. If all the test cases pastor, than it means our code is 100% correct. I hope you got to know the basic understanding of how this code Studio works. Before we start coding, make sure you are clear with the concept of linear search, which I thought in the first video. If you are not clear with it, then I highly recommend, then I highly recommend you to go back to the previous videos and understand the concept of linear search first, thoroughly. And come back here to go. Because once you are clear with the concept, you can easily understand anything. I write the code easily. Because once you are clear with the concept of linear search, you can write code easily without much tension. I hope you understood the problem statement of the linear search as well. That's good. Now let's start coding. On the screen. As you can see on the right side, we have to write out logic. No, they have created a function called linear search, okay? Then they have pastor integers or an integer x, which is the element to be searched in a given array. As discussed in the previous video, the concept we are using for searching the elements in the array. First V such that element in the 0th index, first index, then the second index, and enter the last element of the array. This flow, this concept is called the linear search. In one direction, we are checking that if it is the limit which we are asserting is present in the array or not. Now, here we have to traverse the complete array. For this, we use the for loop. Inside the for-loop, initializing the integer i variable to 0. And in the condition part of the for-loop, we're telling you if I is less than the size of the array. This is nothing but the condition of the for loop. Next part is called as ambition part. I didn't audition part we are writing I plus plus. Now inside the for loop, we have to search the element x. I didn't mind x is nothing but the element to be searched. In this case, we are looking if it is present in the array or not. For that we are. For that we will use the if condition statement. One important thing regarding if statement is inside the if statement. Have to use only the Boolean conditions. If statements do not work for assignment operators. Back to the video. So inside, here, inside if we are writing yada of phi equal to, equal to x, I think I have mentioned a born the equal to, equal to operator. It is basically user for the comparison. But let's understand this era of I equal to, equal to x. Let say at element at 0th index one, I mean the value of 0 index. I mean the element at 0th index is one and element to be searched x, in this case, the value of x is four. No. This line era of phi equal to, equal to x. We are comparing two earned for hard they equal. Gander, tell me, are they equal? Dancer will come as no. Then in condition. If they're equal, then simply written I. I here means index position. Because we are retaining the I here because in the question we are asked to return the position of the next. When you find the element in the array. Let me know in the comment section, if you traveled complete array and you did not find the element in this case x, then what should you do? Should return minus one, right? Because we did not find it as V saw earlier. We do not find 20 in the array. We traverse the complete array and we did not find 20 in it, written minus one. According to the cushion, if we did not find the element x in the array, B have two written minus one. So we will return minus one. We will type minus one, I might write, I hope you have understood. The game is simple. If you find X in the array, then written one on the spot, or if you don't have to travel further. So the game is simple. If you find the X in the dendrite and one on the spot. We don't have two drivers for the because we already, we have already founded. But if we did not find element x after drivers in the complete array, then we have to return minus one. I think this statement is clear to you all. Now, let's run this run button and wait for few seconds. As you can see, we have all the test cases. All the three test cases have been cleared. Now we will hit the ground. I know we will hit on submit. Let's wait for few seconds. Who, Dave, we have biased on their test cases. Thank you for watching this class. I will see you guys in the class would use.