7.1 Linear Search Algorithm with example | linear search in C | Data structures

I'm going to write down a piece of code for this linear search algorithm now first of all I'm going to take one example and we will see the working principle of this linear search see this is also known as sequential search fine now suppose this is our data this is our array having how many elements n is equal to 8 8 elements and indexes from 0 to 7 right now suppose you want to search a data and value of this data or key or you can take any variable I am going to take here data a variable data suppose you want to search 42 you want to search is 42 present in this area or not now here two cases are there one is element is present in the list and second is not present right if element is present now in that case you want you want to print the location of that of that element where that element is present in this array maybe you can say at which index or you can say at which position this element is present so see here the index for this 42 is 5 right and position is what 6th position 1 2 3 4 5 6 6th position right so either you can print index or you can print location now see if element is not present then you want that your program should print element not found so now let us discuss the working of this linear search in this case we are going to start our search from starting of the era from the 0th index fine and we are going to access each element of the array one by one and see whether this is the desired data you want if yes then you are going to return that location if no then you are you next element then to the next element then next next next and like this now see 442 first of all we'll check HERE from the sway we are going to start from the starting of theory 15 is this element same you want know then move to next element this is not 42 next element this is also not 42 this is also not 42 next and next now here you find what 42 now where you are going to stop your search to two cases are there first cases first stopping condition is you found the element like 42 you have found the 42 here now we are going to stop your search algorithm here and now what does this algorithm will return the index 5 that 42 is present at index 5 or second cases if data is not present in there is let us suppose you want to search 41 now here is not 41 here not 41 not 41 now next next is 1 you are going to stop here now because next we don't have any element so now second stopping condition is you have reached to the end of the array fine and the data is not present here so now you have to stop - stopping conditions are there either you find the data are you released till end of the air now how to write down the code for this C you can you can write down the iterative method using for loop or you can write down a function of linear search and you can call that function in your main function either method you can follow fine I'm going to follow here they try to approach I am going to write the for loop see we are going to start a loop from the Sun decks 0th index and the loop will go till end right now see here we have one for loop we will take one variable I I is equal to starting from 0 and I less than n and I plus plus because here n is 8 so it should go till 7:00 less than eight that is from zero to seven fine now next next what you will do you have to find what 42 okay now you will check if if name of fare is a if area of I area of I value would be first of all I will you would be zero then I plus plus then 1 then 2 like this we are going to search now we are going to access each element of the array one by one and we are going to search and we are going to compare is this data we want to search right so if area Phi is equal to equal to data then what you will do you will return the location of that data you will print so here you will print printf you can write here element found add index percentage D and you want to print the index so here you will print what I write ad index so 42 would present at index v if you want to print the position you can say element found at position I plus 1 means at which position sixth position now suppose we are going to write this thing only this is closing of this if this is closing of this for now see let us trace out this code with for this 42 fine I will newest at starting I values 0 I is less than 80 yes we will enter into this loop if a of I a of 0 a of 0 is 15 15 is equal to data data is 42 no so control will not go within this if statement now after if this if the control will go to I plus plus now I is equal to 1 if 1 is equal to data no now I is equal to 2ei of 2 is equal to data no I is equal to 3ei of 3 is equal to this date and no I is equal to 4ei oh four is equal to data no a oh five now see a o5u 5 is 42 42 equal to data is 42 yes now control will go within this loop now what control will print element found at index 5 fine now see the problem is here now again after this if control will go to I plus plus now I is equal to 6 and 6 is less than 8 right now again we are going to check if a of 6 a of 6 is equal to data right but that is not true again I plus plus I is equal to 7 again 7 a of 7 equal to data no we are not going to enter into this loop now again is equal to 8 now 8 less than 8 no now control will go out from this for loop now here the drawback is what for this for drawback is what we have found the element at index v but still still this this cord is searching for 6th location also and for seventh index also now what is the point to search after finding the data right we have we have found the date Ana now at 5th index only we have found 42 now what should be done this this this algorithm or this code should have stopped at here on e but this is not stopping now you have to add one more condition here right you have to write right what break after this printf you'll write break and after you will close this if statement now say this break means what as soon as control will go to this break statement then then what the control will go out from the loop in which break statement is written now it break statement is written any which loop which for loop here so we found the data at index 5 at index 5 right again control will go to here only break break means the control will go out out from this loop out from this loop here only now if you write this break then we will not search for this location and for this location this is the stopping condition now so now next case is if element is not present in the list in the array then what you will do then you will print what element not found right now we are where to write that condition how to write that condition see if element is not present if suppose we are going to search data is equal to 41 and that 41 is not present now finally when I is equal to 7 I is equal to 7 7 is less than 8 data is 41 a of 7 is this 41 no now again I plus plus I is equal to 8 and 8 is less than 8 no now control will go out from this loop whatever you will write here fine it means if I when you has been raised to 8 here it is what a number of element it means if I when nu becomes same as this n value number of elements in that case data is not present you can say right so what you will write here you write if if I evaluate to 2 and in that case you can write here printf element not found and if you don't write this condition if you don't write this 1 1 second method to print this statement is element not found s see you can take one variable here at the starting you can take either found or flower it's up to you I am taking found a variable found is equal to 0 in the program at starting and if you find the element in that case you will do what you and you'll convert this found value to 1 means found is equal to true now we have found the element right so before this break before this break here you will write what found is equal to 1 right here after this after this for if you don't write this condition then second case is this is case one you can write this also this is case two and you can write this also here you can write if found is equal to is equal to zero it means you can print F here data not found if found is equal to zero it means it means control has not entered into this if condition here means this condition never becomes true so that is why that is why after the for loop also still found is equal to 0 it means found is equal to false element is not present so you can write element you can say element not present so you can write this also you can write this also if you follow if you write this case then you do no need to declare this found variable see this is not the complete program so you have to write some another statement so this is just the main logic not the complete program so now what is time complexity first of all we are going to check in best case best case as well suppose this is our array and you want to find out data is equal to 15 by in linear search jewelry we are going to start from the initial point of the array from the 0th index find out check 15 first at first index at 0th index we have value 15 15 is equal to the state yes it means in one comparison only you have got the data so in the best case the time complexity would be order of 1 only what about worst is worst case means suppose you want to find out the data 17 here how many comparisons you have to do first of all 15 then 5 then with 20 then 35 to 40 to 6 to 7 and then 17 and here you got the data means n N Parisians eight comparisons right so that is why here the time complexity in worst cases order up and the number of elements total number of elements and if you find out the time complexity you just you just do what check out where is the loop in this program here we have loop and find out the statements written in this loop how many times they are being executed that is the time complexity fine so see these statements printf and break are only one and one time so this is constant only this if statement this would be executed for how many times maximum this this would repeat for maximum how many times still in right so in worst case time complexity would be and now what about average case have to find out average see average means sum of all the cases divided by number of cases write sum of all the cases how many cases can be there see one case is the data is present in the 0th index only in that case how many time complexity is or how many comparisons are there one only plus if data is present at here only in that case how many comparisons are there two only plus third cases the data is present here only none in that case how many comparisons one two and three like that till n comparisons how many cases some of all the cases right divided by number of cases are n right and I hope you know the formula of this one 1 plus 2 Plus 3 up to n that is n into n plus 1 divided by 2 and here we have n n n so the time complexity will be order of n plus 1 divided by 2 you can say so this is all about linear search in next video I am going to talk about binary search right so till then bye-bye take

Channel: Jenny's lectures CS/IT NET&JRF

Views: 278,534

Rating: 4.8923512 out of 5

Keywords: linear search, search, algorithms, data structures and algorithms, searching, sorting algorithms, searching algorithms, linear search algorithm, linear search in c, data structures, linear search and binary search, what is linear search, jennys lectures, jayanti lamba, jenny lamba, ugc net cs study material, gate, GATE computer science, computer science engineering, information technology, cs/it youtube channels, c programming, code, heap sort, prims algorithm, merge sort

Id: C46QfTjVCNU

Length: 15min 9sec (909 seconds)

Published: Thu Jun 27 2019