• 2 days ago
Transcript
00:00Next time we are going to talk about binary search, we have implemented some kind of code in this way,
00:06this is the same code that we have written in class, we have left a start and a end, we
00:11have left a while loop, which will start to end, every time the first step was to calculate mid, end
00:19plus start by 2, after that we checked, the first case was that if mid is equal to mid, let's
00:23return, the second case was that if my mid is less than mid is less than mid, then I will
00:28shift the start,
00:29and the third case, if my mid is less than mid is less than mid, then I will shift the
00:33end, and if I return my target, I will not get my target, so in this case, I would return
00:40to the minus 1 to signify that my key does not exist in my array,
00:44so in this case, I had implemented in binary search, this is the iterative logic, iterative, i.e. I used
00:54an iteration loop, besides the same binary search, we can also write recursion, in fact, divide and conquer, we had
01:01a question,
01:01how to search in a sorted and rotated array, we have modified binary search using recursion, we can also use
01:11recursion, now we will remove time complexity,
01:14and what we will do, and what we will do, we will remove it, intuitively, intuitively, intuitively,
01:21intuitively, meaning, with some thoughts, with some logic, with some logic, with some practical things, we will remove it from
01:28that way,
01:30so intuitively, if I will see, how do my binary search approach work, every time I have an array, this
01:37array is n size, so what is the input size,
01:40what is the end, this is my first iteration, in the first iteration, what do I have to do, I
01:46have to search my array,
01:48and try to find out my input, after that, what do I do, after that, I divide it in half,
01:54and when I do comparison,
01:55I get to know, what is my middle point key is, or I put it in this half, or I
02:00put it in the left half,
02:02so it is not possible, the key is the one, and it will also be put it in this half,
02:05and it will also be put it in this half,
02:09and then I divide it, and I get to know, or I get to know, or I get to know,
02:11or I get to know, or I get to know,
02:12not, I get to know which half I put it in the half, and I don't have to do this,
02:18and I put the key in this part,
02:20and then I run a second iteration, and then I also put the size of my array, and then I
02:27will have to do half,
02:28and then I will do the same work, I will divide it in half, and I will see that which
02:33one is left half, and right half,
02:36I will put my key in the right half
02:39I will run the third iteration
02:44I will run the third iteration
02:45This time my array size will reduce
02:47The last time I had the end
02:48Then I will have the end by 2
02:50Now I will have the end by 2
02:53What will happen?
02:54I will have the end by 4
02:55I will have half the array
03:00This time I will do the same work
03:02I will remove the midpoint
03:03And I will also half
03:04In the fourth iteration
03:06My array size will be n by 8
03:08And my array will be half
03:09In the same way
03:11My last iteration
03:14What will happen?
03:15In my last iteration
03:17My array size will be 1
03:20And I will have a single element
03:23I will compare it with 1
03:24Or 2
03:25I will compare it with single element
03:27I will compare it with single element
03:31I will compare it with 20
03:33I will compare it with that
03:33Either it is the key
03:35Or it is not
03:37This will be my worst case
03:39The worst case means
03:41In the last iteration I have one element
03:42One element
03:44Every time I have a single element
03:48Now I will compare it with this element
03:51I will compare it with the third tier
03:52I will compare it with the second tier
03:53This will compare it with the third tier
04:10That is my key. But what do I have to do? I have to look at worst case.
04:14In the worst case, I will divide the array and when the last element becomes a single element, this will
04:18be my worst case.
04:19If I analyze the worst case, what do I do in my binary search?
04:24In the binary search, I have to divide my n from this way.
04:29What is the value of my n? My array size. This is my array size.
04:35Or I can say input size.
04:37In every iteration, what is happening here?
04:40This was n. This was n divided by 2 to the bar 1.
04:43This was n divided by 2 to the bar 2.
04:46This was n divided by 4.
04:47This was n divided by 2 to the bar 3.
04:50In this way, there will be a point when n divided by 2 to the bar k.
04:54And this value will have 1.
04:56In the last moment, I will divide n from 2.
05:00How many times do I divide?
05:01How many times do I divide?
05:04n divided by 2 multiplied by k.
05:07Every time I multiply n from 2 to the bar 2 to the bar k.
05:10What can I do?
05:11That I divide n from 2 to the bar k.
05:15And this value will have 1.
05:17I should have a single element in my array.
05:19So I can say that n divided by 2 to the bar k should be equal to 1.
05:23Now, I will remove the k.
05:26This is my 0th iteration.
05:28This is my first iteration.
05:29This is my second iteration.
05:30This is my third iteration.
05:31This is my third iteration.
05:32How many iterations?
05:33k iterations.
05:35k iterations.
05:36k iterations.
05:36If I run this whole loop.
05:38k times run.
05:40First, I will run one time run.
05:41Then I will run two times run.
05:43Then I will run three times run.
05:44And how many times do I work?
05:45In the loop, it is constant.
05:47I know this constant work.
05:48I know this constant work.
05:49I would ignore this for loop.
05:51While loop also.
05:52I will do the same thing.
05:53If I remove this loop, how many times do I run this loop?
05:55And in the loop, it is constant work.
05:56So I will tell you that it will be p.
05:58What do I know?
05:59Time complexity will come.
06:00Time complexity will come.
06:01Time complexity will come.
06:02How many times do I run this loop?
06:04How many times do I run this loop?
06:05Every time my array divide,
06:06I will reach single element.
06:09Now I will remove how many times divide it.
06:10n divided by 2 to the bar k is equal to 1.
06:13If I want to write this equation,
06:15this will be my equation.
06:16n is equal to 2 to the bar k.
06:18How many times do I run this loop?
06:21K iteration.
06:22So I need k value.
06:23What will I get?
06:25I will take log on both sides.
06:27Log base to n is equal to k.
06:30So what is my k value?
06:32Here is my k value.
06:33Log n.
06:34And what is it?
06:35How many times do I run this loop?
06:37The loop runs is equal to k.
06:39So what is the time complexity?
06:41Time complexity comes.
06:42Every time I run my loop.
06:44Multiply by.
06:45How many times do I run this loop?
06:47Let's assume that this loop has run this loop.
06:50So what should I do?
06:52Big of k into p.
06:54Now I know what time complexity is equal to
06:56Big of k value.
06:57Log n.
06:58Multiply with p.
06:59I know my p is constant.
07:01So p will cut from here.
07:02And this will come.
07:03My time complexity binary search.
07:05Big of log n.
07:06So in this way, I say that my binary search time complexity is log n.
07:11Finally, if I talk about my binary search time complexity is log n.
07:16And with that, I compare it with linear search time complexity.
07:20So that was big of n.
07:21If we plot it in the graph.
07:24We plot it in this way.
07:25We plot our time and input size graph.
07:28We plot it in the graph.
07:29In which my n is like this.
07:32My log n time complexity is like this.
07:35My log n time complexity is like this.
07:36Now I analyze here.
07:37It can be a small input.
07:38My linear time is less than my log n time.
07:43But for some big input, my linear time will be more.
07:48As compared to my log n time.
07:50So log n time complexity is a good time complexity for any program.
07:56That's why binary search is a very efficient search.
07:59And using binary search, we write a lot of complex advanced programs.
08:05Now I make a small summary table.
08:07For a little experimental analysis.
08:11Let's say that I have an array.
08:13I have an array.
08:13One is that I will put a linear search on this array.
08:16One is that I will put a binary search on this array.
08:20Let's say that if I put a linear search on this array.
08:22And my array size is 1000.
08:24So for 1000 size array.
08:25If I relate the time complexity and operation with time complexity.
08:29Then it can be in linear.
08:30I have 1000 milliseconds.
08:32If it is 1000 milliseconds.
08:34How many in binary search will be?
08:36In binary search will be log n.
08:37Again, if I can say log of 10 to the power 3.
08:41What is the amount of value?
08:42It is approximately 10.
08:44So here I'll put 10 milliseconds and perform 10 milliseconds.
08:48In millisecond I tell operations.
08:51That there will be about so many operations.
08:54Now I will add n size.
08:55I will add 10 to the power 5.
08:5710 to the power 5.
08:58It is 1,000,000,000.
09:00I can say here that I will take 10 to the power 5 operations.
09:04I will remove this.
09:0610 to the power 5 operations and how many in binary search this figure will be 20
09:1120 how did I log of 10 to the power 5 so this is 5 multiplied by log of 10
09:18log of 10 value is about 3 point something so 3.3 if I take it and multiply it with
09:245
09:24or 3.2 it will not be more than 20 around value and now n value if I do 10
09:31to the power 9
09:31so in linear search 10 to the power 9 operations and what will be in binary search
09:35in binary search 30 figures so here we can see that in linear search
09:4210 to the power 9 size if the area comes in linear search I apply to 10 to the power
09:479
09:47operations can improve and in binary search only 30 operations
09:52how many difference between 10 to the power 9 and 30
09:56I will talk about 1 crore so in 1 crore I think 7 zeros
10:01so it is 10 to the power 7 so here we are talking about 100 crore and 30
10:05so there is so much difference when we talk about big numbers or big input size
10:11so here I have analyzed my linear search
10:14how much inefficient as compared to my binary search
10:17my binary search is so powerful when it comes to searching techniques
10:22now I have to analyze it mathematically and now we have to do it intuitively
10:26intuitively or make a diagram
10:28and understand the logic
10:30what logic is running in code
10:32if I do it mathematically
10:33I can write equations here
10:37what do I can say in mathematics
10:39let me say the equation
10:40let me say the function is t to the power n
10:43this function is time complexity
10:45what I can say
10:46what I can say is that if I have time complexity
10:48or my binary search function
10:50if I have time complexity
10:51if I have time complexity
10:53n input size
10:53that will be equal to
10:55some constant work k
10:57plus n by 2
10:58I have done a constant work
11:00after I have done an array
11:01so now I have to perform binary search
11:03for n by 2 size
11:05now what I can do
11:07if I have to do n by 2
11:08this will be equal to constant work
11:12if I have to do n by 4
11:13if I have to do n by 4
11:15then k plus n by 8
11:18and finally what will happen
11:21t1
11:22I will know
11:23if I have to perform binary search
11:24for a single input
11:26what will happen
11:27k will be equal to 0
11:29if there is no division
11:31then it will be equal to 0
11:32and k will be equal to constant work
11:33now if I add these equations
11:35I will add these equations
11:36so what can I say
11:37that will be cut
11:38from this
11:39from this
11:39from this
11:40from this
11:41from this
11:41from this
11:41from this
11:41from this
11:41from this
11:44if I have to sum
11:46what will happen
11:47time complexity of n is equal to
11:50k
11:50how many times I have to do t
11:53half
11:53half
11:54it has to take value 1
11:56log n times
11:57so how many times this
11:59k will add
11:59k will add
12:00log n times
12:01k into log n times
12:03k into log n times
12:07because k is a constant
12:09we will ignore it
12:10in this way
12:11we will remove the binary search
12:12mathematically
12:12time complexity
12:13we will remove
12:14equations
12:15in which we analyze
12:16every time
12:17what is constant work
12:18and now
12:19what is called for half
12:20for the same function
12:22or the same equation
12:23we will remove
12:23what size
12:24we will remove
12:25from both sides
12:28and add equations
12:30and finally
12:30how many equations
12:31log n equations
12:32because every time
12:33n half
12:33is 1
12:34so as many
12:35k will come
12:36I will do
12:37multiplied by
12:38log n
12:38so my time complexity
12:40will come
12:40to log n
12:41to log n
12:41to log n