7.2 What is binary search | Binary Search Algorithm with example | Data structures

using this binary search will take less time than the linear search right now what is the working principle of this binary search we are going to discuss with the help of an example right now see one prerequisite of this binary search is or you can say the requirement of this binary search algorithm is what the array should be sorted see here you can see I have taken this example but the data in this array is what sorted right if the data is not sorted then you cannot apply binary search on that Eric you have to first sort the array then you can apply binary search for searching so here the precondition for this binary search is the array should be sorted that is not a case in linear search that linear search works fine on the sorted array as well as on unsorted array now we will see how this binary search algorithm will work fine see so now we are going to search for the data or you can say key 59 is this fifty-nine present in this area or not and if present your code should return where this 59 is present the index at which this 59 is present see one more important point about this binary search algorithm is what it is divide and conquer technique it means it is going to divide the array into two half recursively divide the area now how recursively it will divide that into sub arrays we are going to see see in this case we are going to find out the middle element of the array fine so we are going to take two variables first is here left variable and we are going to point left here means L value is 0 next variable is right and the value of this right is 9 or you can say n minus 1 so in this algorithm we are going to find out the mid position of the array from where we are going to divide the area into two halves fine see first of all the left is 0 and the right is 9 in this case now find out the mid of this one how do now mid L plus I divided by 2l plus R divided by 2 and we are going to take the floor value of this one 0 plus 9 divided by 2 is 1 4.5 floor value is 4 so mid is what for so at index 4 we are having mid now now here three cases can be their first cases the data you want to find out is equal to the data at the mid position fine second case is the data is less than the data which is at mid position or third cases the data you want to find out the key you want to find out find out is greater than the data which is at mid position so so these are three cases find data is equal to the Smith data is less than the say of MIT and data is greater than yo from it three cases can be there now see here the data is 59 and mid is 4 now what is that a or for a o for the data is 25 so here the case is this one the data is 59 and 59 is greater than a off mid mid is 25 right so now we can say that this data is present to the right of the Smith in this summary in this submarine now we have divided this array into two parts one is this one and one is this one now we can see this 59 is present to the right of this mid now how you can say this because we know that that array is sorted and if array is sorted then all the data which is greater than 25 must be present to the right of this 25 right now we are going to see we are now we are going to search only in this array we have divided our search space first at first our search spaces this one after first comparison we have divided it into half now this is our search space we are going to search from here to here now fine so if this is the case then this left then this left variable should be moved here on to the right here this side towards the right so now here we have our left or left now becomes mid plus one because we are going to work only in this area now and our is as it is that is nine again leap it the same step find out mid five plus nine fourteen divided by two is seven mid is what seven now now mid is what here seven now again three cases can be there now check data is fifty nine is sixty-three same as 59 no now the case is here 59 is the data is less than 63 this second case data is less than a of mid now what you can say data is present to the left of 63 here only because theta is less than 63 and array sorted so now so now if data is present to the left of me to the left of MIT in that case what you will do left would be as at E is 5 and this right would be moved towards this side so now right becomes mid minus one now here we have right because now we are going to work only in this space here only we again divided the array into two parts that is why I was saying we recursively divide the hair into two parts fine until you find the element so now our is what six mid minus 1 7 minus 1 is 6 now again find out the mid 5 plus 6 is 11 by 2 that is 5 point 5 flow values 5 so mid is now here 5l is also 5 and mid is also 5 now right now check it's 59 same as you've mid no 59 is greater than a of mid it means 59 is present to the right of me to the right area of this mid right and if this this is present the data is present to the right of the mid in that case what what we will do we move left towards this side means left becomes mid plus one now right so left becomes mid plus 1 that is 5 plus 1 is 6 right remains as as it is so now now here we have left and here we have right only so if left and right are at pointing at same index it means in this we have only one element and the array we have not only one element so now we have only 59 see I can find out middle 6 plus 6s and divided by 2 is 6 now made is also here at 6 now check if data is equal to is equal to our mid 59 is equal to EOF mid yes now this is the stopping condition we found the data so now here you are going to stop and you are you are going to return mid return mid means you are going to return the index 6 where the data is present fine so this is the one stopping condition now second case is if data is not present in the array in that case when you are going to stop your searching algorithm let us take that case on that case also is 25 you cut to 59 is this you want to search no so second cases this data this data is what this data is greater than the data which is at mid position so here the case is this one the data is 59 and 59 is greater than a of mid mid is 25 right so now we can say that this data is present to the right of the Smith in this summary in this submarine now we have divided this array into two parts one is this one and one is this one now we can say this 59 is present to the right of this mid now how you can say this because we know that that array is sorted and if array is sorted then all the data which is greater than 25 must be present to the right of this 25 right now we are going to see we are now we are going to search only in this area we have divided our search space first at first our search spaces this one after first comparison we have divided it into half now this is our search space we are going to search from here to here now fine so if this is the case then this left then this left variable should be moved here on to the right here this side towards the right so now here we have our left or left now becomes mid plus one because we are going to work only in this area now and our is as it is that is nine again if it the same step find out mid five plus nine fourteen divided by two is seven meters what seven now now mid is what here seven now again three cases can be there now check that I fifty nine is sixty-three same as fifty nine know now the case is here fifty nine is the data is less than 63 this second case data is less than a of mid now what you can say a data is present to the left of 63 here only because data is less than 63 and array sorted so now so now if data is present to the left of mid to the left of mid in that case what you will do left would be as a T's 5 and this right would be moved towards this side so now right becomes mid minus 1 now here we have right because now we are going to work only in this space here only we again divided the array into two parts that is why I was saying we recursively divide the hair into two parts fine until you find the element so now our is what six mid minus 1 7 minus 1 is 6 now again find out the mid 5 plus 6 is 11 by 2 that is 5 point 5 floor values 5 so mid is now here 5 L is also 5 and mitt is also five now right now check it's 59 same as you've made no 59 is greater than a of mid it means 59 is present to the right of me to the right area of this mid right and if this this is present the data is present to the right of the mid in that case what what we will do will move left towards this side means left becomes mid plus one now right so left becomes mid plus 1 that is 5 plus 1 is 6 right remains has as it is so now now here we have left and here we have right only so if left and right are at pointing at same index it means in this we have only one element and the array we have now only one element so now we have only 59 see I can find out middle 6 plus 6s and divided by 2 is 6 now made is also here at 6 now check if data is equal to is equal to M 859 is equal to EOF mid yes now this is the stopping condition we found the data so now here you are going to stop and your you are going to return mid return bid means you are going to return the index 6 where the data is present fine so this is the one stopping condition now second case is if data is not present in the array in that case when you are going to stop your searching algorithm let us take that case only that case also now let us take you from 1 to find out 60 see 16 is not present here now we will see same ellen's here only and right is here only now left is 0 and right is 9 middays what for at 4 you have what 25 here we have made this is not equal to 60 60 is greater than this 25 so data is present to the right of 25 data is present to the right of this one and we are going move this left and left becomes mid plus one here now left is four plus one is five and right I mean sighs at ease again find out the middle element that is seven now my desert here only now check that I 60 is 60 is equal to 63 a off mid no first case no that is not true data is less than a off mid second case is true if less than it means the data is present to the left of left of 63 then we are going to work in this area left becomes as it is in that case in that case right becomes mid minus one so here we are going to shift this right now right becomes mid minus 1 that is 6 again the middle element that is 5 so now mid is at 5 right here all here we have made now check if data is equal to mid 60 is equal to 45 no 60 is greater than mid this condition is true if greater than if greater then then data would be to the right of this right of mid so in that case we are going to move this left to this side so left this L becomes now mid plus 1 that is 6 and bright remains as it is so now here we have what left and right both now middle element is 6 now middle 6 now here also we have made now check the status 60 is equal to this mid no the 60 is what greater than this data it means the data is present to the right of this 59 right and if data is present to the right array then we are going to move this L L becomes mid plus 1 now L becomes 6 plus 1 is 7 and our remains as it is now this is the stopping condition here if this L value if L value becomes greater than R value it means data is not present here we are going to repeat these steps find out the mid checking these conditions till L less than right because here we have taken left here we have taken right once this left becomes greater than right they have grossed each other it means the data is not present so this is the stopping condition in that case if data is not present right now I am going to write a piece of code for this binary search see I'm going to create a function binary search in this I am going to pass array a total number of elements in the array and the data you want to search so now first of all what we have done we have taken L is equal to 0 and R is equal to n minus 1 n is 10 so our was 9 5 and after that we have calculated what mid so now Mehta is equal to L plus R divided by 2 right after calculating mid we are checked three conditions right three guesses can be there so we have checked if data is equal to is equal to mid if this is true then you do it return mid here you are returning some integer value so the data type would be in right if this condition is not true else if data is less than a of mid if data is less than movement less than EF mid less than means the data is present to the left side of this middle it means our value would be moved l value remains as it is so now R becomes mid minus 1 right and the third case says data is present to the right of the smiddy in that case we will move left left becomes L mid plus 1 else L becomes mid plus 1 right and you are going to repeat these steps in left l is less than R once L becomes greater than R it means data not found right so you are going to repeat these steps so you are going to write down these steps in a loop that is while L is less than R till then these steps should be repeated if L is not less than R it means obviously L would be greater than R so here you can return what minus 1 minus 1 means data is not present right and you can lose this function so this is how the binary search is going to work now what is the time complexity for this algorithm see we are we are reducing the search space by half at first search space was this one again by half again by half again by half like this so if such kind of behavior exists in that case time complexity would always be order of no in worst case it is order of log N and what is the time complexity in best SC suppose I am going to find the data 25 data is 25 at first I am calculating L plus 9 plus 0 divided by 2 that is 4 and at 4 is Medus at 4 now here only I got 25 so this is 1 the best case in best is time complexity would be order of 1 right and in worst case it is order of log n see now why I am saying this order of log and I am going to tell you with the help of an example see let us take these two cases I am just going to take these two for loops simple for loop so I am going to calculate the time complexity for this and this also time complexity means we are going to find out within this for loop the statements is going to Institute how many times right that is the time complexity now in this case in this case how many times the statement within this for loop would be executed see I is equal to 1 I less than 100 here n is equal to 100 here also n is equal to 100 fine so this is going to be executed now I into 2 here I'm going to double the value I so now next time becomes I value becomes to two is also less than hundred now again it would be executed now next time it becomes four four is also less than hundred now next time it becomes eight next 16 32 64 and after that it becomes what 128 128 and 128 is not less than hundred so this is not going to be executed so how many times this statement will be executed one two three four five six seven seven times and anybody was hundred for the value hundred how many times the statement would be executed only for seven times right same here in this case and value is 100 how many times this one peg is equal to dead first I is equal to 100 now I am going to divide the I value by two I am going to divide it by half next time 50 50 is greater than equal to one okay next is 25 25 is also two it would be executed next time divided by two is two n next time six next time three next time one next time if you divide it becomes what 0 0 is not greater than equal to one so it is going to stop it is not going to execute now here also 7 times 1 2 3 4 5 6 7 7 times here also n value is 100 right I hope you know the formula of this thing log of base B and n is equal to K it means it means this be B of B power K is equal to n right this is the formula if this is the case then you can say that B of K is equal to and if you if this is the case B of K is equal to 1 it means you can say log of P n is equal to K now here n is equal to 100 now if you put logos 2 and hundred so what you can write 2 raised to power 2 raise to power what 7 because 2 raised to power 6 is what at 64 and 64 is not so I can write 2 raised to power sin that is twenty-eight so I can write seven but I cannot write 6 because 64 is less than hundred but greater than value we can write so we can take hair to raise to power approximately 7 so it means it becomes what 7 all right because base is also 2 and here also 2 it means we just take only the power that is 7 fine so the time complexity how many times this loop has been executed log n times right here also you can say log n times so if such kind of behavior occurs if loop is going to doubles or loop is going to half in that case always the time complexity is order of log n so in binary search also we are going to divide the space by half then again half then again half so this is the case so the time complexity would be log n here and this log n is far better than the order of n that is the time complexity of linear search that is why I was I was saying saying saying that this is the most popular searching algorithm because of this time complexity only in the worst case the time complexity is order of Lohman in average case also the time complexity or time complexity is order of log n so this is all about binary search I hope you got this concept why we are writing the code like this maybe this this case can be little bit confusing why we are taking the time complexity log n but I hope you got this fine so I'll see in the next video till then bye bye take

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

Views: 306,313

Rating: 4.9066539 out of 5

Keywords: binary search, linear search, search, searching algorithms, sorting algorithms, algorithms, data structures, jenny's lectures, jenny lamba, c programming, quick sort, algorithm, heap, heap sort, time complexity of linear search, linear search algorithm, search algorithms, linear search in c, time complexity of binary search, ugc net, computer science, gate, GATE computer science, study material, engineering, jayanti khatri lamba, prims algorithm, merge sort, insertion sort

Id: V_T5NuccwRA

Length: 23min 30sec (1410 seconds)

Published: Fri Jun 28 2019