1
00:00:00,230 --> 00:00:06,770
Hey there and welcome back now for solving the longest increasing subsequence question.

2
00:00:06,770 --> 00:00:11,090
There is another approach which uses the binary search.

3
00:00:11,090 --> 00:00:18,530
Now over here I am including this solution as well for the sake of completeness, but please do check

4
00:00:18,530 --> 00:00:23,120
out the other video where we discuss binary search in detail.

5
00:00:23,120 --> 00:00:28,820
But in this part we are going to implement the solution with the binary search as well.

6
00:00:28,820 --> 00:00:36,230
And for this approach that we are going to discuss, you could implement the solution with just normal

7
00:00:36,230 --> 00:00:36,620
search.

8
00:00:36,620 --> 00:00:43,280
And remember searching for a value in an array with just normal search by iterating over all the elements

9
00:00:43,280 --> 00:00:45,320
is an O of n operation.

10
00:00:45,320 --> 00:00:52,220
But if we do the search with binary search, we get a better time complexity, which is O of log n.

11
00:00:52,220 --> 00:00:57,260
Now, because binary search has a better time complexity than ordinary search.

12
00:00:57,260 --> 00:01:02,930
Using binary search in this approach will give us a better time complexity.

13
00:01:02,930 --> 00:01:05,390
So let's get started with this approach.