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 the 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.
Binary Search Algorithm in C++ with Source Code Example…
How recursively it will divide that into sub-arrays we are going to 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 to 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 nowhere 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 the mid position or third cases the data you want to find out the key you want to find out is greater than the data which is at mid position. 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 midis 4 now what is that a or for ao for the data is 25 so here the case is this one the data is 59 and 59 is greater than an off mid is 25 right.
Binary Search Algorithm:
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 the 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 the 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 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 mid is what here seven now again three cases can be there now check data is fifty-nine is sixty-three same as 59. C++ projects for beginners with source code
The case is here 59 is the data is less than 63 this second case data is less than an of mid. 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 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 points 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 an of mid it means 59 is present to the right of me to the right area of this mid-right and if this is present the data is present to the right of the mid in that case 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 it is so now here.
We have left and here we have right only so if left and right are at pointing at the 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 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 going to 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 is what this data is greater than the data which is at the mid position so here the case is this one the data is 59 and 59 is greater than an of 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…Continue With code Example…
