1
00:00:00,550 --> 00:00:01,540
Welcome back.

2
00:00:01,540 --> 00:00:07,300
Let's now go ahead and code the solution, which we discussed in the previous video, to search in the

3
00:00:07,300 --> 00:00:09,130
matrix for a target value.

4
00:00:09,130 --> 00:00:11,830
So let's call this function search in matrix.

5
00:00:11,830 --> 00:00:16,030
Now this function is going to take in the matrix and the target value.

6
00:00:16,030 --> 00:00:20,770
And remember the matrix is just a two dimensional array or an array of arrays.

7
00:00:20,770 --> 00:00:23,680
That is an array where each element is an array itself.

8
00:00:23,680 --> 00:00:24,160
All right.

9
00:00:24,190 --> 00:00:29,860
Now we are going to do one binary search to identify the row in which the target value can be there,

10
00:00:29,860 --> 00:00:31,060
if at all it is there.

11
00:00:31,060 --> 00:00:36,640
And then we will do one more binary search on that particular row to identify whether that target value

12
00:00:36,640 --> 00:00:37,420
is there or not.

13
00:00:37,420 --> 00:00:38,950
So this is how we are going to proceed.

14
00:00:38,950 --> 00:00:43,750
Now, to start with, let's just identify the number of columns and rows in the matrix.

15
00:00:43,750 --> 00:00:51,550
So we can say const columns is equal to matrix at zero dot length.

16
00:00:52,180 --> 00:00:52,540
Right.

17
00:00:52,540 --> 00:00:55,210
This is the length of one of the elements of the matrix.

18
00:00:55,210 --> 00:01:00,190
And in the question as per the question, every array is going to have the same number of elements.

19
00:01:00,190 --> 00:01:02,950
And let's also go ahead and find the rows.

20
00:01:02,950 --> 00:01:06,970
So we can say const rows is equal to matrix dot length.

21
00:01:06,970 --> 00:01:10,750
So the number of elements in the row will give us the number of rows.

22
00:01:10,750 --> 00:01:11,230
All right.

23
00:01:11,230 --> 00:01:16,420
So we find the columns and the rows in the matrix or the two dimensional array which is given to us.

24
00:01:16,420 --> 00:01:21,340
Now let's go ahead and start the binary search to identify the row.

25
00:01:24,090 --> 00:01:24,540
All right.

26
00:01:24,540 --> 00:01:30,630
So let's say top is equal to zero and then bottom.

27
00:01:31,740 --> 00:01:36,240
Is going to be the number of rows minus one because it's zero indexed, right?

28
00:01:36,240 --> 00:01:37,260
So top is zero.

29
00:01:37,260 --> 00:01:39,900
So bottom has to be number of rows minus one.

30
00:01:39,900 --> 00:01:40,380
All right.

31
00:01:40,380 --> 00:01:42,810
So we are again doing the binary search over here.

32
00:01:42,810 --> 00:01:43,110
All right.

33
00:01:43,110 --> 00:01:44,220
So we'll have a while loop.

34
00:01:44,220 --> 00:01:47,100
So while top less than equal to bottom.

35
00:01:47,100 --> 00:01:48,420
And then we'll keep looping.

36
00:01:48,420 --> 00:01:49,980
So this is how we go about it.

37
00:01:49,980 --> 00:01:52,710
Now let's also have a variable middle.

38
00:01:52,710 --> 00:01:54,330
Let me initialize this over here.

39
00:01:54,630 --> 00:01:55,050
All right.

40
00:01:55,050 --> 00:01:58,050
So once inside the while loop we will calculate middle.

41
00:01:58,050 --> 00:02:00,840
Middle is going to be math dot floor.

42
00:02:01,810 --> 00:02:04,990
Top plus bottom divided by two.

43
00:02:08,440 --> 00:02:08,950
All right.

44
00:02:08,950 --> 00:02:11,320
So we are going to find the middle row.

45
00:02:11,320 --> 00:02:17,650
Now what we will do is we will check the beginning and the that is the first and the last element in

46
00:02:17,650 --> 00:02:18,850
this particular row.

47
00:02:18,850 --> 00:02:19,840
So let's check.

48
00:02:19,840 --> 00:02:21,400
So if target.

49
00:02:22,110 --> 00:02:27,540
Is less than the first element in this row that is matrix at row middle.

50
00:02:29,060 --> 00:02:34,670
And at index zero in that particular array, because we know that matrix at middle this over here will

51
00:02:34,670 --> 00:02:35,540
give us an array.

52
00:02:35,570 --> 00:02:39,410
Now in this array we are going to check the zeroth index element.

53
00:02:39,410 --> 00:02:41,720
Now that's the lowest element in this array.

54
00:02:41,720 --> 00:02:47,660
Right now if target is less than this element over here that is the zeroth element at the element at

55
00:02:47,660 --> 00:02:51,050
index zero in the middle row of the matrix.

56
00:02:51,050 --> 00:02:56,270
If target is less than this value, then we are going to change bottom because we only need to look

57
00:02:56,270 --> 00:02:58,640
at from top till middle minus one.

58
00:02:58,640 --> 00:03:01,550
So bottom is going to change to middle minus one.

59
00:03:01,550 --> 00:03:03,020
So this is binary search right.

60
00:03:03,020 --> 00:03:05,540
So you can see that this is nothing but binary search.

61
00:03:05,540 --> 00:03:06,830
Now let's proceed.

62
00:03:06,830 --> 00:03:14,210
Else if this is not the case that is if target is greater than the largest value in the row middle that

63
00:03:14,210 --> 00:03:16,400
is matrix at middle.

64
00:03:17,730 --> 00:03:21,060
And the index would be the number of columns minus one.

65
00:03:21,060 --> 00:03:24,660
So we are doing minus one over here because the columns are zero indexed.

66
00:03:24,660 --> 00:03:24,990
Right.

67
00:03:24,990 --> 00:03:27,090
So the first over here is zero.

68
00:03:27,090 --> 00:03:30,570
That's why even though there are column number of columns.

69
00:03:30,570 --> 00:03:35,730
So we have identified the number of columns we have to do minus one over here to get to the last index

70
00:03:35,730 --> 00:03:37,080
in this particular row.

71
00:03:37,080 --> 00:03:43,410
Now if target is greater than this value over here then we can we only need to look at the rows which

72
00:03:43,410 --> 00:03:46,350
are greater which which are which are below this particular row.

73
00:03:46,350 --> 00:03:46,620
Right.

74
00:03:46,620 --> 00:03:54,690
Because we have we, we have seen that the rows are sorted from left to right, and the last value of

75
00:03:54,690 --> 00:03:58,800
a row will be less than the first value of the next row.

76
00:03:58,800 --> 00:03:59,670
So we have seen that right.

77
00:03:59,670 --> 00:04:02,070
So for example let's just visualize this over here.

78
00:04:02,070 --> 00:04:05,910
Let's say the matrix is having the values one, two and three.

79
00:04:05,910 --> 00:04:09,960
And in the next row it's four five and six.

80
00:04:09,960 --> 00:04:13,650
And let's say in the next row it's seven eight and nine.

81
00:04:13,650 --> 00:04:17,430
For example, we are let's say we are searching for element eight.

82
00:04:17,460 --> 00:04:20,550
Now middle as per this would be this row.

83
00:04:20,550 --> 00:04:23,130
Now over here the last element is six.

84
00:04:23,130 --> 00:04:25,770
Now target which is eight is greater than this six.

85
00:04:25,770 --> 00:04:25,980
Right.

86
00:04:25,980 --> 00:04:28,380
So we only need to look at rows which are below it.

87
00:04:28,380 --> 00:04:30,240
So that means we can change top.

88
00:04:30,240 --> 00:04:33,030
So we can change top to middle plus one.

89
00:04:33,390 --> 00:04:35,880
So you can see that this is nothing but binary search.

90
00:04:35,880 --> 00:04:40,350
Now if this is also not the case else that is if target is within the range.

91
00:04:40,350 --> 00:04:46,140
So target is not less than the lowest value and target is not greater than the largest value.

92
00:04:46,140 --> 00:04:51,900
If that is the case, then we can just break out and we have identified the relevant row in which we

93
00:04:51,900 --> 00:04:54,360
need to have our next binary search.

94
00:04:54,360 --> 00:04:54,840
All right.

95
00:04:54,870 --> 00:05:00,660
Now, once we are outside this while loop, let's just have a check whether top is greater than bottom

96
00:05:00,660 --> 00:05:00,930
right.

97
00:05:00,930 --> 00:05:04,140
So there are two ways that we can come out of this while loop.

98
00:05:04,140 --> 00:05:08,700
One is through this break right where, which means that we have identified the relevant row.

99
00:05:08,700 --> 00:05:13,860
And the second way to break out is, is if top is no longer less than equal to bottom.

100
00:05:13,860 --> 00:05:19,050
So if top is no longer less than equal to bottom, when we come out of this while loop, that means

101
00:05:19,050 --> 00:05:25,950
that the target value is not there in the given 2D matrix, 2D array, or matrix, and we can just return

102
00:05:25,950 --> 00:05:26,580
false.

103
00:05:27,730 --> 00:05:28,150
All right.

104
00:05:28,150 --> 00:05:34,450
Now, if this is not the case, that means that we only need to check in the middle row, the row which

105
00:05:34,450 --> 00:05:36,610
is in the variable middle right.

106
00:05:36,610 --> 00:05:39,520
So because we have seen that we have we have broken out over here.

107
00:05:39,520 --> 00:05:45,820
So that means that target is in between the lowest and the largest value of that particular row.

108
00:05:45,820 --> 00:05:52,060
So let's again go ahead and do one more binary search on the row which is now stored in the variable

109
00:05:52,060 --> 00:05:52,570
middle.

110
00:05:52,570 --> 00:05:53,710
So let's go ahead and do that.

111
00:05:53,710 --> 00:05:56,620
So for this let's have two variables let's say left.

112
00:05:56,620 --> 00:05:58,390
So left is going to be equal to zero.

113
00:05:58,390 --> 00:05:59,590
And then we'll have right.

114
00:05:59,590 --> 00:06:02,830
So right is going to be the number of columns minus one.

115
00:06:02,830 --> 00:06:05,620
So this is again just normal binary search.

116
00:06:05,620 --> 00:06:07,330
Now let's also have one more variable.

117
00:06:07,330 --> 00:06:09,460
Let's just initialize it to mid value.

118
00:06:10,480 --> 00:06:12,340
All right, now we'll have a while loop.

119
00:06:12,340 --> 00:06:16,720
Now this is going to loop as long as left less than equal to right.

120
00:06:17,630 --> 00:06:21,980
Now inside this while loop over here we are going to calculate the mid value.

121
00:06:21,980 --> 00:06:25,670
And mid value is going to be equal to math dot floor.

122
00:06:27,170 --> 00:06:31,190
Left plus right divided by two.

123
00:06:32,200 --> 00:06:33,880
So we have found the mid value.

124
00:06:33,880 --> 00:06:41,560
Now we are going to check whether the target value is equal to the value in the middle row at this index

125
00:06:41,560 --> 00:06:42,610
which is mid value.

126
00:06:42,610 --> 00:06:43,660
So let's just check that.

127
00:06:43,660 --> 00:06:45,400
So if target.

128
00:06:46,780 --> 00:06:51,040
Is equal to matrix at row middle.

129
00:06:51,820 --> 00:06:55,180
And at index mid value in this particular row.

130
00:06:55,180 --> 00:06:55,570
Right.

131
00:06:55,570 --> 00:07:00,790
So if this is equal to target then we can just return true because we have found the value.

132
00:07:00,790 --> 00:07:02,740
Now if this is not so let's proceed.

133
00:07:02,740 --> 00:07:04,780
So else if target.

134
00:07:05,480 --> 00:07:08,210
Is less than whatever we have over here.

135
00:07:08,210 --> 00:07:11,870
Matrix at the row middle at index mid value.

136
00:07:11,870 --> 00:07:18,410
So if target is less than this then we only need to look towards the left part from the mid value right.

137
00:07:18,410 --> 00:07:24,290
So we can say that right is going to be equal to mid value minus one.

138
00:07:24,290 --> 00:07:29,840
And if that is not the case that is if target is greater than this value over here that is matrix at

139
00:07:29,840 --> 00:07:34,070
row middle and column mid value or index mid value in that particular array.

140
00:07:34,070 --> 00:07:39,950
If target is greater than that, then we only need to look towards the right of mid value, which means

141
00:07:39,950 --> 00:07:44,570
that we can set left is equal to mid value plus one.

142
00:07:44,990 --> 00:07:45,260
All right.

143
00:07:45,260 --> 00:07:46,610
So this is just binary search.

144
00:07:46,610 --> 00:07:48,140
So we have done this before.

145
00:07:48,140 --> 00:07:54,800
Now once we are out of this and if we have not returned true then it means that left became greater

146
00:07:54,800 --> 00:07:55,220
than right.

147
00:07:55,220 --> 00:07:58,700
And we were not able to find the target value in that particular row.

148
00:07:58,700 --> 00:08:00,800
And then we can just return false.

149
00:08:01,460 --> 00:08:02,150
So that's it.

150
00:08:02,150 --> 00:08:03,650
So this is the function.

151
00:08:03,650 --> 00:08:05,900
So let's go ahead and test our function.

152
00:08:05,900 --> 00:08:08,690
So let's call this function search matrix.

153
00:08:08,690 --> 00:08:10,400
And let's have an array also.

154
00:08:10,400 --> 00:08:10,640
All right.

155
00:08:10,640 --> 00:08:11,810
So let's just have an array.

156
00:08:11,810 --> 00:08:13,190
Let me just write this over here.

157
00:08:13,190 --> 00:08:16,220
So for example let's have 123 4 in 1 row.

158
00:08:16,220 --> 00:08:17,690
And let's have.

159
00:08:18,360 --> 00:08:23,610
Five, six, seven and eight in the next row.

160
00:08:24,030 --> 00:08:29,340
And let's have nine, ten, 11 and 12 in the third row.

161
00:08:29,340 --> 00:08:30,360
And let's have one more row.

162
00:08:30,360 --> 00:08:36,660
So let's have, let's say 20, 30, 40 and 50 in the last row.

163
00:08:36,660 --> 00:08:38,310
So this is going to be our matrix.

164
00:08:38,310 --> 00:08:41,370
So you can see the matrix will have four elements.

165
00:08:41,370 --> 00:08:44,670
And each element is going to be an array with four values.

166
00:08:44,670 --> 00:08:46,770
So let's go ahead and define our matrix array.

167
00:08:46,770 --> 00:08:52,020
So matrix is equal to and the first element is 1234.

168
00:08:52,470 --> 00:08:57,150
The second element is 5678.

169
00:08:57,660 --> 00:09:03,300
The third element is 910 1112.

170
00:09:03,420 --> 00:09:10,380
And the last element is going to be 2030, 40 and 50.

171
00:09:10,380 --> 00:09:10,920
All right.

172
00:09:10,920 --> 00:09:15,300
So we are going to search for this in in this matrix for a particular value.

173
00:09:15,300 --> 00:09:17,760
So our function is search in matrix.

174
00:09:17,760 --> 00:09:21,300
So let's call our function and let's pass in the matrix.

175
00:09:21,300 --> 00:09:23,940
And let's say we are searching for the value 12.

176
00:09:23,940 --> 00:09:28,860
Now our expectation is that we should get true because you can see it's there in our matrix.

177
00:09:28,860 --> 00:09:30,420
So let's go ahead and search for it.

178
00:09:31,680 --> 00:09:34,110
And you can see we are getting true, which is correct.

179
00:09:34,140 --> 00:09:36,120
Now what if we are searching for 60?

180
00:09:36,150 --> 00:09:38,250
It should give us false because it's not there.

181
00:09:38,670 --> 00:09:40,890
And yes, you can see we are getting false.

182
00:09:40,920 --> 00:09:42,930
What if we are searching for one?

183
00:09:45,740 --> 00:09:47,060
It should give us true.

184
00:09:47,060 --> 00:09:47,870
So we get true?

185
00:09:47,870 --> 00:09:48,140
Yes.

186
00:09:48,140 --> 00:09:49,520
So our function is working.

187
00:09:49,520 --> 00:09:52,400
Now let's go ahead and walk through the code.

188
00:09:52,400 --> 00:09:53,390
Let's take an example.

189
00:09:53,390 --> 00:09:57,080
Let's say we are searching for the value 40 or let's say we are searching for three.

190
00:09:57,080 --> 00:09:57,440
All right.

191
00:09:57,440 --> 00:09:59,420
So let's say we are searching for the value three.

192
00:09:59,420 --> 00:10:03,590
Now let's take this example and walk through the code which we have just now written.

193
00:10:04,280 --> 00:10:04,760
All right.

194
00:10:04,760 --> 00:10:06,710
So we have this matrix.

195
00:10:06,710 --> 00:10:09,380
And the value for which we are searching is three.

196
00:10:09,380 --> 00:10:10,730
Now we are calling the function.

197
00:10:10,730 --> 00:10:11,840
So we come over here.

198
00:10:11,840 --> 00:10:15,170
Now let let me just write parallelly along with this.

199
00:10:15,170 --> 00:10:17,240
So we find the number of columns over here.

200
00:10:17,240 --> 00:10:20,870
Now we see we have seen over here below that there are four columns right.

201
00:10:20,870 --> 00:10:22,730
So we have one two, three four.

202
00:10:22,730 --> 00:10:24,890
So the number of columns is equal to four.

203
00:10:24,890 --> 00:10:26,210
So let's just write that over here.

204
00:10:26,210 --> 00:10:27,710
And the number of rows.

205
00:10:27,710 --> 00:10:28,880
What about the number of rows.

206
00:10:28,880 --> 00:10:30,110
Let's check that over here.

207
00:10:30,110 --> 00:10:32,300
We have 123 and four.

208
00:10:32,300 --> 00:10:33,590
We have four rows right.

209
00:10:33,590 --> 00:10:34,580
So these four rows.

210
00:10:34,580 --> 00:10:37,190
So the number of rows is also equal to four.

211
00:10:37,960 --> 00:10:39,250
And then we come over here.

212
00:10:39,250 --> 00:10:44,830
Top is equal to zero and bottom is going to be equal to three because rose is four right.

213
00:10:44,830 --> 00:10:47,800
So bottom is three and top is equal to zero.

214
00:10:47,800 --> 00:10:50,500
And then we see that zero less than equal to three.

215
00:10:50,500 --> 00:10:51,160
That's true three.

216
00:10:51,160 --> 00:10:54,280
So we come inside the while loop and we're going to calculate middle.

217
00:10:54,280 --> 00:10:56,800
Middle is going to be zero plus three divided by two.

218
00:10:56,800 --> 00:10:57,850
And then we have flooring it.

219
00:10:57,850 --> 00:10:59,170
So that's equal to one.

220
00:10:59,170 --> 00:11:00,670
So middle is equal to one.

221
00:11:00,670 --> 00:11:04,690
Now in the row middle that is matrix at one right.

222
00:11:04,690 --> 00:11:07,630
So we are going to take the zeroth index element.

223
00:11:07,630 --> 00:11:09,760
And we are checking if target is less than this.

224
00:11:09,760 --> 00:11:10,990
So let's take a look at it.

225
00:11:10,990 --> 00:11:14,380
So we have the row one which is this row over here.

226
00:11:14,380 --> 00:11:16,420
And the zeroth index we have five.

227
00:11:16,420 --> 00:11:18,430
So is target less than five.

228
00:11:18,430 --> 00:11:19,480
Yes target is three.

229
00:11:19,480 --> 00:11:21,040
So target is less than five right.

230
00:11:21,040 --> 00:11:22,300
So yes that's true.

231
00:11:22,300 --> 00:11:28,360
So we go ahead and over here we are setting bottom is equal to middle minus one which is equal to zero.

232
00:11:28,360 --> 00:11:29,920
So bottom is equal to zero.

233
00:11:29,920 --> 00:11:34,600
Again we come over here top is zero and bottom is zero and zero equal to zero.

234
00:11:34,600 --> 00:11:35,200
So that's true.

235
00:11:35,350 --> 00:11:38,230
So we come inside and we calculate again middle right.

236
00:11:38,230 --> 00:11:39,580
So we calculate middle again.

237
00:11:39,580 --> 00:11:40,930
Now at this point.

238
00:11:41,830 --> 00:11:46,420
Middle is going to be equal to zero plus zero divided by two, which is zero itself.

239
00:11:46,420 --> 00:11:46,750
Right?

240
00:11:46,750 --> 00:11:48,220
So middle is zero.

241
00:11:48,220 --> 00:11:51,160
Now again we are checking matrix at zero.

242
00:11:51,160 --> 00:11:55,390
That is we are taking the array at the index zero which is 1234.

243
00:11:55,390 --> 00:11:57,100
So we have the array 1234.

244
00:11:57,100 --> 00:11:58,750
So let me just write this over here.

245
00:11:58,750 --> 00:12:02,830
So this over here matrix at zero is the array 1234.

246
00:12:02,860 --> 00:12:07,900
Now we are taking the element at the zeroth index which is one and target is three.

247
00:12:07,900 --> 00:12:09,340
So is three less than one.

248
00:12:09,340 --> 00:12:10,120
No that's false.

249
00:12:10,240 --> 00:12:10,930
So this is false.

250
00:12:10,930 --> 00:12:11,290
See.

251
00:12:11,320 --> 00:12:17,650
Now we are checking over here is target greater than matrix at zero which is this array at columns minus

252
00:12:17,650 --> 00:12:17,860
one.

253
00:12:17,860 --> 00:12:21,280
So columns is equal to four four minus one is three which is this index.

254
00:12:21,280 --> 00:12:21,760
Over here.

255
00:12:21,760 --> 00:12:22,900
Now is three.

256
00:12:22,930 --> 00:12:24,070
The target is three.

257
00:12:24,070 --> 00:12:25,930
Which is the target greater than four.

258
00:12:25,930 --> 00:12:27,070
No that's also false.

259
00:12:27,190 --> 00:12:29,200
So we don't go ahead over here.

260
00:12:29,200 --> 00:12:31,870
And then we come to this part and then we break out.

261
00:12:31,870 --> 00:12:32,260
All right.

262
00:12:32,260 --> 00:12:34,750
So at this point middle is equal to zero.

263
00:12:34,750 --> 00:12:36,010
And we have broken out.

264
00:12:36,010 --> 00:12:39,580
Now top is zero and bottom is also equal to zero.

265
00:12:39,580 --> 00:12:40,150
All right.

266
00:12:40,180 --> 00:12:45,520
Now once we come out of this while loop over here we check if top is greater than bottom.

267
00:12:45,520 --> 00:12:48,070
We have seen that top is zero and bottom is zero.

268
00:12:48,070 --> 00:12:50,230
So top is not greater than bottom.

269
00:12:50,230 --> 00:12:51,580
So we don't return false.

270
00:12:51,580 --> 00:12:51,970
All right.

271
00:12:51,970 --> 00:12:56,860
So that means we have identified the row in which we can have the target value.

272
00:12:56,860 --> 00:13:00,220
Again it's not necessary that the target value is there in that row.

273
00:13:00,220 --> 00:13:04,990
But if it is there in the matrix it can only be there in that particular row.

274
00:13:04,990 --> 00:13:07,930
Now we come over here we said left is equal to zero.

275
00:13:07,930 --> 00:13:11,770
And we said right is equal to columns minus one which is equal to three.

276
00:13:11,770 --> 00:13:15,850
So left is pointing over here this is index 012 and three.

277
00:13:15,850 --> 00:13:17,980
And right is pointing at index three.

278
00:13:17,980 --> 00:13:20,140
Now it's just a normal binary search right.

279
00:13:20,140 --> 00:13:23,140
So we are having the variable mid value over here.

280
00:13:24,180 --> 00:13:27,900
And we calculate mid value which is left plus right divided by two.

281
00:13:27,930 --> 00:13:29,490
So zero plus three by two.

282
00:13:29,520 --> 00:13:30,420
That gives us.

283
00:13:30,420 --> 00:13:32,310
And when we floor it it gives us one.

284
00:13:32,310 --> 00:13:34,830
So middle is pointing to index one.

285
00:13:34,830 --> 00:13:37,530
Now we are checking if target is equal to middle.

286
00:13:37,530 --> 00:13:40,440
And we see that target was three right.

287
00:13:40,440 --> 00:13:42,660
So target is not equal to the value at middle.

288
00:13:42,660 --> 00:13:45,210
So we see that target is greater than this value.

289
00:13:45,210 --> 00:13:47,220
So we are going to change the left pointer.

290
00:13:47,220 --> 00:13:49,680
The left pointer is changed to middle plus one.

291
00:13:49,680 --> 00:13:51,600
So left is pointing to index two.

292
00:13:51,600 --> 00:13:53,070
Right is pointing to index three.

293
00:13:53,070 --> 00:13:56,310
So we calculate the new middle which is two plus three divided by two.

294
00:13:56,310 --> 00:13:57,390
And then we are flooring it.

295
00:13:57,390 --> 00:14:00,870
So middle is also going to going to point at index two.

296
00:14:00,870 --> 00:14:07,980
And we see that target is equal to the matrix at row zero and the middle value which is two.

297
00:14:08,010 --> 00:14:11,490
So we have found the target value and we will return true.

298
00:14:11,490 --> 00:14:13,500
And this is how the code works.

299
00:14:13,500 --> 00:14:14,100
All right.

300
00:14:14,130 --> 00:14:18,450
Now let's take a quick look at the space and time complexity of our solution.

301
00:14:18,450 --> 00:14:25,140
Now in the function which is search index search in matrix you can see that over here we are implementing

302
00:14:25,140 --> 00:14:28,980
once the binary search to identify the relevant row right.

303
00:14:29,100 --> 00:14:29,910
This part over here.

304
00:14:29,910 --> 00:14:36,690
So over here we are going to do O of log m operations where m is the number of rows.

305
00:14:39,160 --> 00:14:39,850
All right.

306
00:14:40,610 --> 00:14:46,280
And then once this is done, we are also doing one more binary search in this part.

307
00:14:47,470 --> 00:14:52,060
Which is the normal binary search, which you have seen previously, to identify whether the target

308
00:14:52,060 --> 00:14:54,970
value is there in the row that we have identified.

309
00:14:55,000 --> 00:15:00,880
Now this is going to be doing O of log n operation, where n is the number of columns.

310
00:15:00,880 --> 00:15:01,240
Right.

311
00:15:01,240 --> 00:15:04,690
Because in one array they are going to be n elements.

312
00:15:05,020 --> 00:15:11,740
So that's why we can say that the time complexity of this solution is O of log m plus log n and log

313
00:15:11,740 --> 00:15:15,310
m plus log n is nothing but log m n.

314
00:15:16,970 --> 00:15:20,330
So log n plus log n is log m into n.

315
00:15:21,550 --> 00:15:27,220
That's why the time complexity of this solution is o of log m n, and you can see that we are not using

316
00:15:27,220 --> 00:15:28,270
any extra space.

317
00:15:28,270 --> 00:15:31,750
So the space complexity is equal to O of one.

318
00:15:31,750 --> 00:15:34,450
Or this solution runs in constant space.