In this course on Data Structures and Algorithms, we have seen a lot so far. In today's video we are going to talk about: linear search and binary search. What is Linear Search? And what is binary search? Today's video will tell you guys in a little more detail Although I gave a little idea to you guys in this video. The third or fourth video that I made Video was made on Best Case, Worst Case and Average case analysis In that I gave you a very good idea, What is linear search and what is binary search.

But today we are going to code it here, because it is asked a lot. And here I can't ignore it So here quickly I will tell you about linear and binary search. So first of all I grab a pen, and show you guys here by making an array. So look, let's start the story from here Let's say you have an array: well, this is your array: Here I am creating an array and here is my array like this, and inside it let's say some elements As if it is inside 4, it is inside 8 here 10, 12, 15 There can be many elements inside an array, okay! And whether it is sorted or unsorted, I don't care about that.

And I have to do an element search for what is here, 2, 8 and that's 2, well, I found the search 2 What have I found, search for this element So what if I want to search for this element, in this array So I'm going to search all the indices one by one to see if there is 2 over 0, no, is there 2 here, no Is there a 2 here, no, is there a 2 here, no Is there a 2 here, no, is there a 2 here, no Yes, there is 2 so i'd say, ok here's 2 2 found But if 2 could not be found here, that is, I could not find 2 then I would say that I could not find 2 in this array ok, and when will I say this when i traverse to the end of the array So the linear searching that happens, I write here, which is our linear search. that is done through array traversal ok, so let me write here, this is done through array traversal The meaning of traversal was told to you people that we do this by visiting all the elements.

And we do array traversal But we stop the array traversal if we find the element So we stop the array traversal at that whenever we get our element, ok This Linear Search: Very Simple Search If I give you a lot of cards in real life, I give you a deck of card And I say that you take out 6 of hearts in it So you may only do linear search, well, you will do linear search only. Now let's say I give you 6 of Hearts, I say these cards are a lot of cards: this dude take me 6 of Hearts out of this What will you say, you will say it is okay You will keep falling cards one by one, as soon as you get 6 of heart you say you have got it So what did you do, you did linear search So it's you, wait I'll make you better, I also wear shoes for you And you did this linear search Now I will give you a very good example of binary search that when you will do binary search So the linear search is very simple, quite a straight forward algorithm to find all the elements of the array one by one: Where the element is found, it has to be said that the element is found, and the search is over.

Or if you reach the end of the array, then you have to say that the search is over: the element could not be found, that's the end, that's all. ok So this was our linear search what will i do here now I will make a line, and tell you guys here binary search So let me extend this line a bit. And here now I will tell binary search, below this line so what is binary search Binary search is a slightly smarter algorithm. How much smart algorithm is it? a little smart algorithm what does it do By the way, I will tell that this our linear search:, it will work for sorted arrays, will also work for unsorted arrays And the reason is clear that why will it, why will it Because these cards are sorted, what difference does it make to you if they are unsorted? You have to find 6 of hearts, keep falling one by one finish, you will get card somewhere, ok So this thing is clear to us Now what I am going to tell you people here is: A smart algorithm named Binary Search what does binary search do Before explaining what binary search does, I will give you a real life example.

Then you will understand better What will I do to you in real life example? I want to give you people in real life example, Let's say I give you a book, what do I give, I give a book i will give you a book In this I say that open the page number 38, or show it by opening page number 238. Suppose it has thousand pages ok That's a thousand pages, and I'm saying I want page number 238 in this, okay. So will you turn every page of the book? I want you guys to tell me how the example looks I want you guys to comment below and tell me how this example looks I will also give such examples in future And even if you don't want an example, tell Example is you have a book, and this book has been given to you people, you have been told that 238 page no. should be opened inside it There are thousand pages in this book, and you have to open 238 page no. so the first thing you do is open a random page Most probably you open the page with the center So you have come to page number 500 Now you have 2 parts: of the book What did you do, opened the book: One is the part of you that opened your book, that: this part of you, look, I opened the book: here You see in the diagram, I have opened the book And one part you have this one, and one part this one So divided that book into 2 parts And this page no.

What is open: in this book that is 500 Now you know that 238 is less than 500 then you will half it back What will you do now, you will half this part too And you will come to page no. 250 Now you know that, what is 238 is less than 250 so what will you do? Come back a little bit and you guys will come to the page number 238 means you will converge If you turned the pages one by one, you would have to turn 238 pages. And how many pages did you turn over here? Instead of getting 1.2.3.2.4.5.6 you will do with your intuition Is this a binary search algorithm? This binary search algorithm works in a very similar way Now here you guys also put your intuition You also see here that how much less than 250, 38 is just a little less.

So whatever you have, turn 4 pages, turn 8 pages little by little. You converge, and you will get this 238 page number How computer will solve this problem first of all, would you have been able to open this 238 page number, if its pages were stitched at random, like the book? without being stitched from 1 to 1000, This pages would have been stitched randomly, then you would not be able to do this Then you can't do 238 page number so what is the first condition of binary search, the condition is, should be sorted array Okay.

Sorted array Array must be sorted, okay Array must be sorted what the array needs to be, the array needs to be sorted this is its first condition Now what I will do here is to make an array or make a sorted array, Infact I will create a sorted array and put some elements inside a sorted array So let's say here I am putting 2, here I am putting 8, Putting here 14, putting here 32, putting here 66 After this, as if I am putting another element in it.

Which is a little bigger, which is 100 After that let's say I'm putting 104 and so on You can add any number of elements Now I say search 8 in it, ok search 8 in this array when i say search 8 in this array So you can also do linear search, you can also do binary search Here if you do a linear search then you are lucky. So here you will find the element in the second search So linear search will be better if you are doing 8 searches here But let us say we are searching 100, Okay. And I'll make this array a little bit bigger And I put 200 here, I put 400 here too This is what you will get: Linear Search easily But if I'm saying 200, search for you, then what will happen? When I am telling you to search 200, then you have to travel the whole array almost to get 200 Now some elements are such that if we search for them, we will find them in linear search. Like 2, 8 will get it very easily But as the size of the array increases, this linear search will become difficult for us.

That's why we do binary search, if the array is sorted then If the array is sorted then we take advantage of this Take advantage of the array being sorted, and do a binary search And what will binary search tell us, I will tell you how it works It works just like I took the example of the book But here's a little bit to you guys, because we're just about to code: That's why I have to tell you people a little more easily, well and in such a way that you guys are able to code. So look, we first consider the first one as Low, okay And we accept the last element as High Okay! So it's Low, it's High, okay. What will I do now, I will take out the mid, what will be the mid greatest integer of (Low + High)/2 greatest integer of (Low + High)/2 Here (8+0)/2 =4, so it will be the mid ok i got it mid What happened, it's my mid, here I got my mid So I'll keep track of three things here I'll keep track of the low, which is my low One will keep the track of high, will keep track of mid So here I am making a table Low, High, and Mid, OK So look over here what's my low You guys see, what's my low my low is 0 here right now and what is high, is 8 And what happened to the mid, became 4 Okay! Now I'll see what if I'm looking for 200 I am searching for 200 now, I have been searching for 8, I am searching for 200 now, okay And I write here that I am searching for 200, I am doing this search 200 here Here I put its tag, I write it completely after doing this, okay So, low, high and mid here I have given these values: Now tell me where 200 will be will be between mid and high or between low and mid Obviously it will be between mid and high Because the mid one is smaller than 200, now less than 200 Now if mid becomes equal to 200 then my search is over, okay If mid is equal to 200 then my search is over but my search is not over yet I'll make the mid here the low over here So I would say now my mid is low And my high is what it is, okay And now I will calculate the new mid So what will I do to with low, I will do 4 And what will I do to the high, my high will remain the same and I calculate the mid (8+4)/2= 6 My mid turns 6, so this will be my mid, ok So I write it here like this, it is my mid now Now tell me where would it be 200 Now tell me where would you guys have been 200 The value that is 104 is less than 200: OK, smaller than 200: a value of 104 So what will I do, I will make this mid low back from Like I made this mid, low This high was let back to be high now i will make this mid, low why will I make this mid, low? I am making this mid, low because I know that my search is to be in this space, in this space.

Here it is my search space: What am I doing to my search space? getting smaller First there was a search space for the whole array, then I halved it, then I halved that array too, then I halved that array too And look over here, it's done as low and I'll let it stay high again Okay Now tell me what will happen low, I have made mid to low, So low will be 6 what will be high, will be 8 And what will be the new mid, you will do the new mid (8+6)/2= 7 So the new mid will be 7 And at every step we are checking this, element found or not, Element found. When our mid was 4, there was element found!, No when our mid was 6, there was element found!, No when our mid is 7, then element found!, Yes Our search is over, and we found the element here in just 3 steps Where we would have done in 7 steps, we found our element in 3 steps So, Hope's Binary Search and Linear Search will be clear to you.

I know in this course I repeated myself a little over here But this repetition is not a useless repetition: these things are so important, if they will sit in the minds of you people. then it will be very beneficial So that's why I showed this thing, linear search and binary search step by step here Earlier I had told you a little theory on the board. But here I showed you guys by making an array, completing it. Now let's code this thing and go to our visual studio code and write the code So, I have made for you guys, some hand written notes with my own hands Well summarize up Linear vs Binary Search: For you guys Surely everyone must read this, access this, Downloading from the description, you will get the link somewhere When I upload the video, it takes me some time to put the notes on the website. So if you watch the video when it is uploaded directly then allow me 5 to 10 minutes or sometimes half an hour, I put the notes, I take time You will find the notes on the website Now if you guys go to the website and do open the DS algo, so man, I do everything according to my own, right here And I try to do everything in time, put the video, then after that here I have to put the notes.

Enough work gets done, so i need my time So hope you guys understand this thing, you understand So what will I do here now, I'll come to the notes The way I told linear search, binary search on one note In the same way I told you people here also: Linear Search and Binary Search So you guys read this, it's a very one pager it's just a one page: Linear and binary search in one page is summarized here So I don't want to read out This is what I told I Didn't Talk About Time Complexity Worst Case Linear search would have been O(n) Binary search would have been O(log n) I did not talk about this, here it is a little important to tell it So look at this, which is our Linear Search and Binary Search : What do we people have to do, if you are looking at linear search, then its complexity is O(n) Because this for an (n) size of array, (n) elements that are traversing. But if you look here binary search So I'm halving the array until it runs out, does not converge speak the same (log n), ok So here you people will not face any issue, okay So this thing must have been cleared to you guys, I hope And here's what I'll do now that I will come in my own VS code Here I open my code part, I have created a separate folder for the code.

And what will I do after opening it, I will create a new file here and i'll name it, This is my video number, If i'm not wrong this is my video number, number 12 I see this is my video number 12 So this is my video number 12 And in video number 12, what will I do here I am showing you people by doing here I am video number 12 12_linearbinarysearch.c, Okay.

So, I created this file: using Linear and Binary search.c I put the boiler plate code here, okay I put my boiler plate code here And now I will do linear search code first, which is very easy So int linearSearch and it will take an array So here I will write, this taking an integer array And at the same time, I would say that (int size), this size is being taken (int size) So it is taking the integer array and at the same time it is taking the size of the array, and at the same time it will take the element of the array what will it do after that this will run a for loop and how long will the for loop run till the size of the array the for loop will run till it finds the element So I would say that as soon as (arr[i]==element) what you do, do return 1 Return 1 means I have got this element here in the array Or I will do one thing that I will return only the index of the array where I have got Otherwise, what will i do otherwise i will return -1 So let's see here whether it works or not Here I am giving (int arr[ ]=) an array in which I am giving some elements And here I put 56, I put a semicolon (;) and what will i do with that, int searched or i will write, int searchindex = linear search And I'll give it the array, and with that the size of the array, and the element I'll put in it Now I have to find out the size of the array, so I will tell you a way to get the size of the array.

So to get the size of the array you can do, int size = sizeof(arr)/sizeof(int) So this way if you don't want to count the elements of the array So you can get the size of the array like this, Okay. So what will I do here, I will give the size and then I'll put a printf i would say, ("The element %d was found that index %d \n") And I'll write the element here and the index here, okay Write the element, write the index, put a semicolon (;) So this is the array: I passed this, I passed it to the size What did I do after this, I passed the element to be searched so i'm doing a work here element = 4; And the index here will be the search index I am returning the result of linear search in the form of search index. So, int element = 4; Okay So here I run and see it and as soon as i run it you guys look, The element 4 was found at index 4 So is it true, 0,1,2,3,4, yes it is true Can I search for element 54 which is not there? so is it giving me -1 It should give -1, but it is saying that element 54 was found at index 4, which is wrong ok so here i should put the element I was passing the 4, I should pass Element Now it will give -1 over here, as you guys can see So how did we code the linear search, let's see one more time Okay! I made a function called linear search to which I passed the array, I passed the size of the array After that I passed the element which I want to search I ran the for loop over the entire array, I said if the array becomes (i = element) as soon as the element is found, while traversing this array Then you return the index where that element was found Otherwise what you do, else you return -1 If we come to the end while searching in this array then you return -1 You should know that as this return i; is written, the function terminates and returns The function's activation record in this stack gets lost.

And this is whatever value it is, It returns and resumes main. So the value of this will come in the search index, whatever it will return It can also be -1, it can also be the index of an array And here's the linear search which will be successful now. Take a look here This is the array it is not sorted So if I am running linear search in this array, it will be sorted even then the linear search will run, Linear search will run even if it is unsorted But if the array is sorted then I will not do linear search, I will do binary search.

Since my array is sorted, I can take advantage of that, I can save time. Now you will not know the time for 10-15 elements, But for 10 to 20,000 elements, you will find that the time is taking a lot of time: in linear searching. Binary searching will take you less time So let's code binary search as well. The linear search was very straight forward I told you here that you go one by one, one after the other, one after the other, do whatever you want with the element, and what you will get here You have to get what your element is ok So, hope you guys have understood this thing, that what is linear search.

Traverse all the elements one by one And as soon as the element is found, you return its index, If the element is not found then return -1, the story is over Okay! Let's do the Binary search now To write the code of binary search I will write here int binarysearch And I am telling you one thing, your responsibility of getting the array sorted is yours If you run your binary search and the array is not sorted So you will get ridiculous results, okay.

So the array must be sorted It becomes the responsibility of you people Now as I told you people in binary search that you guys have to maintain three things 1 thing you have to maintain, 1 thing you have to maintain mid And you have to maintain 1 low and maintain 1 high So what will i do, I will write, int mid = first i will write, int mid, int high, int low Okay. I'll do the low, mid and high, okay So low, mid and high I made here: in my binary search function and what will i do after that, first i will write mid = (low + high)/2 And don't forget to put the brackets even by mistake, you guys must put the brackets And here the greatest integer will by default the (C) language What I mean is that if you will do (5 + 6)/2, Then it would be 11/2 After that it will give you 5 automatically. C language Since it is an integer, the operation between 2 integers will be an integer.

So you don't care about the greatest integer Directly, even if you write like this, It will automatically take that greatest integer. 5 point something will not be this value for 5 and 6 This value will be 5 only, you know this from the C language If you have still problems with C language, So i speak again, Please revise C language, you guys will revise it parallelly. Keep watching this course also, I am not saying that leave this course and go away But you guys take my this learn seen 1 video with notes Take his notes man at least, if you are not watching the video then take notes. With great effort, and very well I have made these notes I made my dream notes, which I once thought that if I had notes, I would make this Made the notes: I gave you people, definitely access it Let's come back from here in the code I updated the mid And I updated the mid, and after updated the mid what i will do here, i will check So I'll check here that (arr[mid] == element) is done If it is done then return it to mid, because this is the index that I want But if it hasn't happened, it hasn't happened, then check it.

(arr[mid]) which : is smaller than : or greater than element if(arr[mid]<element) What will I do then, who will I update if (arr[mid]<element), tell me If there's a less than element, I'll update whom Here I show you in the notebook If it's less than mid Now here's the Greater than mid:, So, so who will I update i will update, update my low now the (arr[mid]<element), Okay. So which one I was updating, when smaller than element : i was updating the low Look, my (arr[mid]) was smaller than the element 66, so I brought the low here, so that's why I'll update the low i would say, low = what will i do to low, low = mid+1; Now why I did (mid+1), you will say why I did not (mid) So you guys look over here it's the mid: not an element This mid element is not mine So here I can't find it, I know So I'm not going to search inclusive from here I will search from 100, ok I will search from 100 till here, ok So this is what I told you, I told you guys Just for convenience, but here I can go more smarter because at 66, I will not get anything So I'll go here, I'll search from here ok So I will do it (mid+1), because i don't mean to take it inclusive, I know : not even here : element Elements are from here to here right now, well, I know that So from here till here my element is there, I know this So now I will take the array from 100 to 400 in consideration, and repeat the same thing with him But what would happen So what if my mid was above 200, i.e.

In this half? Who would I update then, then I would raise my high on (mid-1) Because there is no element on the mid There is no element on the mid So I'll bring him on (mid-1) but why on (mid-1)? i will give you an example as if we were searching for 8 instead of 200 Okay Who would have been searching instead of 200, searching for 8 Look carefully here, Because It will not understand again Searching for 8, and mid would have been 66, which is greater than 8 who do i update then Then I know here that my search is not in this half, it has to be in this half. That's why what's mid is it, make it high But I don't bring the high to 66, I bring the high to 32, Why bring it to 32, because I know that this 66 element is not what I am looking for So I bring it here so (mid-1) ok so high will become (mid-1), So (high = mid-1), Okay So here I write it So else, otherwise what will happen i would write, (high = mid-1), Okay Try to understand these things Try a dry run, make a table like this I know it takes hard work to make a table like this But make, if you make, you will understand clearly If you don't make it, how will you understand, you people will have to make it, you will have to do some hard work, okay So here I made it (else) , put inside the (else) Now, now tell me how long will we keep doing this work From here, I write here, comment to till here How long will we keep doing this We'll keep doing this until (low<=high) is done, okay Now if low and high are converged it means the element which is not available to me Either the low and the high become equal, or the low that is, becomes greater than the high So, as long as it's short to high, I'll keep searching.

Otherwise, I will stop searching either i want to get the element or not If element is to be found then it will return while loop, ok. what will happen, this while loop will return But if I don't get the element: what will happen then If I don't want to get the element then I will return -1 So if I have to get the element then it will return directly here ok, then the code below will not execute again But if return-1 needs to be executed So it just means that the return didn't happen inside this while loop it has not returned inside the while loop. This means it needed to come out and return it means i didn't get the element inside the array That's why return -1 So let's run this man for an array And the way I drove here, Okay.

I write here Unsorted array for linear search Now what will I do here, I will replicate it below and i would say Sorted Array for Binary Search, ok. Sorted array for binary search and doing it like this, 1, 3, 5, 56 or 64, 73 and after that 123 Then 225, then 444, that's all we keep the elements, ok I've only kept the elements and here I got the size of the array. Now I will do binary search instead of linear search, ok And I'll do a binary search and what element am I searching for, I'm searching 56, let's say, okay? So I'm searching 56, and running this code And here's what happened that I didn't print. What happened this I did search index is equal to binary search arr, size, element.

So here I am seeing what is the problem ok so the problem has come that I have to initialize the low first low = 0; After that i have to high = (arr[size – 1]), Okay. what to do (arr[size – 1]) That is, what is high will be my last element. So, I have to do this thing over here. Now, I run it And just now I ran it and it's working until (low<=high) I did this, ughh Sorry, I didn't here (arr[size – 1]), only have to [size – 1] I am making a little mistake, which are my low and high: those are my indexes. So I had to do [Size – 1] over here Look here, element 55 was found at index 3 So a small mistake would have been: Sometimes, okay So, I have to keep (low = 0) Because there is low, that is the index, Not an element, it's an index this is low, low is 0 High is 8, High is not 400, High is 8, so high = 8, look here so what happened now low, mid and high, 56 is saying Your index number at 3, is 0, 1, 2, 3 search 64 and see 64 should come to 4 over here So here I want 4 to come, index comes to 4, that's right Binary search did the right thing.

Can i search for 1, let's see if i can search for 1 or not, Yes i can search 1 also, i was found at index 0. Can i search 444, If I search 444, then it will come on which index? it's coming at 8 0, 1, 2, 3, 4, 5, 6, 7, 8 Absolutely perfect, absolutely perfect Brilliant, Enjoyed here we coded linear search as it is Binary search has also been coded in very simple language. Here I just remove the searching and searching starts. And i will write here, Keep searching until low and high converges Okay Until low <= high, Here I write it like this So here you people have understood linear search, you people have understood binary search Now I have done this to you with coding.

Because it is asked too much, it is asked a lot. Linear Search, Binary Search, You will be asked to enter the code in interviews And I am telling that the probability of asking question question is very high, very high. Linear search O(n), Binary search O(log n) Even the big companies, they also start with this question. Why does start with this questions? If you are going for an advanced interview then you can expect this question That's because, what will happen that first of all they search whether you know basic First of all it will be seen what you are Do you know a little bit about algorithms or did you just increase your grades by bringing marks, in some way you had the exam for the interview, you cleared it, or somehow you got that interview, through referral or by any means. So first he will do a basic search in you and questions like this will be asked in it It will say a sorted array, which algorithm would you use to search? Linear or Binary Or else he will not tell you linear or binary, he will say that you have to search, tell which one you will apply So your answer will depend on whether your second round of interview is coming or not.

Whether it is going to be the second round of the interview or not it will depend on your answer, ok So hope you understand If you give such simple question answer Then the interviewer will ask to you: one step ahead Tell it, let's tell it now, let's tell it now So all these things matter a lot So that's why I have given you this along with the code Now what you will get, where may I give it, I will tell you You will get this PDF, you will find it here I am updating, here the whole course:, updating the content Many people had requested that that you also bring distraction free reading here.

So that too I brought here If you do the show player then this video will be seen, If you do a Hide player then it will be visible to you, in this phone too. So this responsive website: You can now hide player here too And you can do the show player, what you will see in this way I hope you understand this And what shall I do here now? I'll upgrade a code for you guys here, on the website And along with that I have written the notes here hand written.

By the way, reading from Hand written only But I am putting it by typing too, so I am making everything available. So dear to you, many people are saying that we are downloading notes, so zip file is being downloaded, so zip file, we are not able to extract in phone So I would like to tell them that there are some apps, which are helping you to extract zip file.

So you can do that But where the material is not much, I have tried: Directly updating the PDF only As you will see, if you open it, the PDF is opening directly. So I will just say this to you people that you download them on the computer and transfer them in the phone. You guys can adjust a little bit If you have phone which is such: in which you are not able to extract Well you will be able to, if you don't know, to extract So I'm talking about then I hope this course is helpful for you guys Please share this course with your friends If you do this then to bring you such videos for you people it will be very easy for me.

I just want now at this point that everyone should know that the course is going on here, because whoever is coming here He is saying "OH My God" this course is also going on here, It is going so well, everything is going well, I wish I had found this playlist earlier So I want the playlist to reach the people as soon as possible, because I also think that man, people are not coming And the interest of the people is less in the course So earlier also at one time with me, I tell you very transparently I am telling you people that there were many much courses which I used to tell.

And the four views that came to me on a course, and my mind used to go haywire that man If nobody is watching then why am i making So I used to get four views, the fifth one didn't even come, I kept refreshing the page. So it is the same if you take if you share the content, if you think it will be of great benefit. That's all for now in this video Don't forget to like the video Thankyou so much guys for watching this video and I'll see you next time..