1
00:00:00,620 --> 00:00:01,610
Welcome back.

2
00:00:01,610 --> 00:00:06,020
In this video, let's try to think how we can solve this question for this.

3
00:00:06,020 --> 00:00:09,290
First let's develop some intuition regarding the solution.

4
00:00:09,290 --> 00:00:12,560
So over here let's take an example 123456.

5
00:00:12,560 --> 00:00:17,300
And let's go ahead and write all the possible rotations for this array which is given to us.

6
00:00:17,300 --> 00:00:20,870
So one possibility is 612345 right.

7
00:00:20,870 --> 00:00:23,720
Another possibility is 561234.

8
00:00:23,750 --> 00:00:29,960
Then we can have 456123 and 345612 is another possibility.

9
00:00:29,960 --> 00:00:33,710
And finally we also can have two, three, four, five, six and one.

10
00:00:33,710 --> 00:00:35,600
So these are the various possibilities.

11
00:00:35,600 --> 00:00:37,610
Now over here this is index zero.

12
00:00:37,610 --> 00:00:38,450
This is index one.

13
00:00:38,450 --> 00:00:39,410
This is index two.

14
00:00:39,440 --> 00:00:40,490
This is index three.

15
00:00:40,490 --> 00:00:42,800
This is index four and this is index five.

16
00:00:42,800 --> 00:00:48,530
Now previously like we have seen in the case of binary search we will be finding the middle value which

17
00:00:48,530 --> 00:00:50,480
is left plus right divided by two.

18
00:00:50,480 --> 00:00:51,530
And then we are floating it.

19
00:00:51,530 --> 00:00:56,030
So over here that would be zero plus five divided by two which is 2.5.

20
00:00:56,030 --> 00:00:58,040
And when we float it we will get two.

21
00:00:58,070 --> 00:01:00,980
So the middle value is going to be at index two.

22
00:01:01,010 --> 00:01:04,670
So let's just circle the middle value in all of these possibilities.

23
00:01:04,670 --> 00:01:06,650
So these are the various cases.

24
00:01:06,650 --> 00:01:09,350
Now let's make an interesting observation.

25
00:01:09,350 --> 00:01:12,800
If the left value the value at the left index.

26
00:01:12,800 --> 00:01:19,460
If this value over here is less than the value at the middle index, then you can see that the left

27
00:01:19,460 --> 00:01:21,500
part is always sorted.

28
00:01:21,500 --> 00:01:26,270
For example, over here you can see that one is less than three and this part is sorted.

29
00:01:26,270 --> 00:01:28,400
Similarly, four is less than six.

30
00:01:28,400 --> 00:01:30,590
So this part over here is sorted right.

31
00:01:30,590 --> 00:01:32,210
Similarly three is less than five.

32
00:01:32,210 --> 00:01:34,490
So this part is sorted two is less than four.

33
00:01:34,490 --> 00:01:36,020
So this part is sorted.

34
00:01:36,020 --> 00:01:39,470
So we will make use of this property to solve this question.

35
00:01:39,470 --> 00:01:45,470
Now if this is not the case that is if left is the value at the left index is not less than the value

36
00:01:45,470 --> 00:01:48,410
at the middle index, which is the case for example over here.

37
00:01:48,410 --> 00:01:48,560
Right.

38
00:01:48,560 --> 00:01:51,650
You have six over here and two over here or over here.

39
00:01:51,650 --> 00:01:53,270
You have five over here and one over here.

40
00:01:53,270 --> 00:01:57,260
So in these two cases you can see that the right part is sorted.

41
00:01:57,260 --> 00:02:00,770
So if this is not the case then the right part is sorted.

42
00:02:00,770 --> 00:02:02,450
So this is an interesting observation.

43
00:02:02,450 --> 00:02:06,800
So in these two cases these sections are sorted which is the right part.

44
00:02:06,800 --> 00:02:11,600
Now you will also see that this part over here 456 is also sorted.

45
00:02:11,600 --> 00:02:14,660
Similarly five six is sorted and 123 is sorted.

46
00:02:14,660 --> 00:02:18,230
This is the case where the left value is less than the middle value.

47
00:02:18,230 --> 00:02:23,060
So we know that the left part is sorted, but you can observe that the right part is also sorted.

48
00:02:23,060 --> 00:02:26,930
But we cannot use this to solve this question because this is not uniform.

49
00:02:26,930 --> 00:02:28,160
This is not always true.

50
00:02:28,160 --> 00:02:28,370
Right?

51
00:02:28,370 --> 00:02:33,620
For example, over here you can see that you have three and four which is similar to this, right?

52
00:02:33,620 --> 00:02:35,510
You have three which is less than five over here.

53
00:02:35,510 --> 00:02:37,070
So the left part again is sorted.

54
00:02:37,070 --> 00:02:39,170
But you can see the right part is not sorted.

55
00:02:39,170 --> 00:02:40,610
So we cannot make use of this.

56
00:02:40,610 --> 00:02:40,910
Right.

57
00:02:40,910 --> 00:02:46,820
But this is true if the value at the left index is less than the value at the middle index, then always

58
00:02:46,820 --> 00:02:48,140
the left part is sorted.

59
00:02:48,140 --> 00:02:52,310
And if this is not the case, then always the right part is sorted.

60
00:02:52,310 --> 00:02:55,520
So we will make use of this property to solve this question.

61
00:02:55,520 --> 00:02:57,080
All right so let's proceed.

62
00:02:57,080 --> 00:03:02,810
And again over here let me just call this as the m which is m which is the middle.

63
00:03:02,810 --> 00:03:03,230
All right.

64
00:03:03,230 --> 00:03:05,990
And whatever is left to it is the left part.

65
00:03:05,990 --> 00:03:08,840
And whatever is right to it is the right part.

66
00:03:08,840 --> 00:03:09,320
All right.

67
00:03:09,350 --> 00:03:14,300
Now let's go ahead and write the pseudocode of how we can go ahead and solve this question.

68
00:03:14,300 --> 00:03:20,630
Now first, as we do in the case of the binary search, we will have a left pointer and we will have

69
00:03:20,630 --> 00:03:21,530
a right pointer.

70
00:03:21,530 --> 00:03:23,840
And we will calculate the middle index.

71
00:03:23,840 --> 00:03:28,610
Now we are going to check if the value at the middle index is equal to the target value.

72
00:03:28,610 --> 00:03:33,110
If it is equal, then we can stop because we have found the target value.

73
00:03:33,110 --> 00:03:33,530
All right.

74
00:03:33,530 --> 00:03:36,620
Now if this is not equal then we proceed.

75
00:03:36,620 --> 00:03:41,870
First we have to identify whether the left part or the right part is sorted.

76
00:03:41,870 --> 00:03:47,330
And we have seen that either the left part or the right part in this case will definitely be sorted.

77
00:03:47,330 --> 00:03:49,430
One of these two will definitely be sorted.

78
00:03:49,430 --> 00:03:52,880
So first we are going to identify which part is sorted.

79
00:03:52,880 --> 00:03:58,580
So if the value at the left index is less than the value at the middle index, then we know that the

80
00:03:58,580 --> 00:03:59,630
left part is sorted.

81
00:03:59,630 --> 00:04:03,560
And if that is not the case, we know that the right part is sorted.

82
00:04:03,560 --> 00:04:05,300
So we are going to check this over here.

83
00:04:05,300 --> 00:04:05,660
All right.

84
00:04:05,660 --> 00:04:10,190
And then when we write the code over here we are going to check less than equal to because there will

85
00:04:10,190 --> 00:04:15,290
be a case where the left index and the middle index is going to be pointing at the same place.

86
00:04:15,290 --> 00:04:15,500
Right.

87
00:04:15,500 --> 00:04:17,930
So we still want to proceed in that case.

88
00:04:17,930 --> 00:04:22,160
So over here we are going to check if the value at the left index is less than equal to the value of

89
00:04:22,160 --> 00:04:22,940
the middle index.

90
00:04:22,940 --> 00:04:27,770
If that is the case we know the left part is sorted, else we know that the right part is sorted.

91
00:04:27,770 --> 00:04:28,130
All right.

92
00:04:28,130 --> 00:04:29,000
So that's the step.

93
00:04:29,000 --> 00:04:29,990
That's the first step.

94
00:04:29,990 --> 00:04:32,480
Now let's say the left part is sorted.

95
00:04:32,480 --> 00:04:38,300
If the left part is sorted we are going to decide should I explore the left part or should I eliminate

96
00:04:38,300 --> 00:04:38,960
the left part.

97
00:04:38,960 --> 00:04:45,470
So for this I'm going to check whether the target value is in between the two extremes, which is the

98
00:04:45,470 --> 00:04:48,260
value over here and the value over here.

99
00:04:48,260 --> 00:04:51,680
Because if this is sorted, then this is going to be the least value.

100
00:04:51,680 --> 00:04:55,280
And whatever we have over here has to be greater than anything which we have over here.

101
00:04:55,280 --> 00:04:55,580
Right.

102
00:04:55,580 --> 00:05:00,020
So that is what we're going to check if value at the left part less than equal.

103
00:05:00,130 --> 00:05:03,370
Call to the target value less than value at the middle part.

104
00:05:03,520 --> 00:05:07,360
That means that the target value is in between these two values, right?

105
00:05:07,360 --> 00:05:11,740
So then if that is the case, then we will explore the left part.

106
00:05:11,740 --> 00:05:14,620
That means we are eliminating the right part.

107
00:05:14,620 --> 00:05:18,490
So the whole right part or almost half of the input is eliminated.

108
00:05:18,490 --> 00:05:20,140
Now again we proceed.

109
00:05:20,140 --> 00:05:21,550
If this is not the case right.

110
00:05:21,550 --> 00:05:27,130
If the value is not in between these two, then we can be sure that the target value is not present

111
00:05:27,130 --> 00:05:29,410
over here because this part over here is sorted.

112
00:05:29,410 --> 00:05:29,710
Right.

113
00:05:29,710 --> 00:05:35,440
So in that case we will explore the right part or we are eliminating the left part.

114
00:05:35,440 --> 00:05:41,230
So you can see that we are eliminating half of the input in this case, which is what we are doing in

115
00:05:41,230 --> 00:05:46,510
a algorithm with O of log n time complexity, which is the same thing that we did in the case of binary

116
00:05:46,510 --> 00:05:46,990
search.

117
00:05:46,990 --> 00:05:47,500
All right.

118
00:05:47,500 --> 00:05:51,190
So if the left part is sorted we go ahead in this manner.

119
00:05:51,190 --> 00:05:51,670
Now.

120
00:05:51,670 --> 00:05:57,730
Else that is if the right part is sorted again we are going to check if the value at the middle index

121
00:05:57,730 --> 00:06:02,460
is less than the target value, which is less than or equal to the value at the right index.

122
00:06:02,460 --> 00:06:06,540
So again we are checking if the target value is in between these two values.

123
00:06:06,540 --> 00:06:09,570
If so, then we explore the right part.

124
00:06:09,570 --> 00:06:11,400
That means we are eliminating the left part.

125
00:06:11,400 --> 00:06:16,860
Now, if the target is not in between these two values, then we can just eliminate this part and we

126
00:06:16,860 --> 00:06:18,780
will explore the left part.

127
00:06:19,110 --> 00:06:20,340
So this is how we are doing.

128
00:06:20,340 --> 00:06:22,110
Now let me just repeat once more.

129
00:06:22,140 --> 00:06:26,220
The first step is we are going to check if the value at the middle index is equal to target.

130
00:06:26,220 --> 00:06:30,780
If that is the case, then we can just return right because we have identified the target.

131
00:06:30,780 --> 00:06:32,730
So we can return the middle index.

132
00:06:32,730 --> 00:06:38,760
Now if this is not the case, the second step is to identify whether the left part or the right part

133
00:06:38,760 --> 00:06:39,330
is sorted.

134
00:06:39,330 --> 00:06:40,440
So that's the second step.

135
00:06:40,440 --> 00:06:41,850
Which part is sorted.

136
00:06:41,850 --> 00:06:43,050
Let me just write that over here.

137
00:06:43,050 --> 00:06:44,550
Which part is sorted?

138
00:06:46,120 --> 00:06:52,780
Now, if the left part is sorted, we are going to decide whether we should eliminate the left part

139
00:06:52,780 --> 00:06:55,030
or whether we should explore the left part.

140
00:06:55,030 --> 00:06:56,260
So that is what we're doing over here.

141
00:06:56,290 --> 00:06:58,540
Now if the left part is sorted.

142
00:06:58,540 --> 00:06:59,980
So that's what is happening over here.

143
00:06:59,980 --> 00:07:07,240
If the target value is in between the value at the left index and the value at the right index, that

144
00:07:07,240 --> 00:07:12,100
means the target value is somewhere over here, possibly somewhere over here, if at all present.

145
00:07:12,100 --> 00:07:15,460
In that case, we are going to explore the left part.

146
00:07:15,460 --> 00:07:18,190
That means we are eliminating the right part.

147
00:07:18,190 --> 00:07:23,860
But if the value is not between these two, and because we know that this part over here is sorted,

148
00:07:23,860 --> 00:07:27,580
then we can just eliminate the left part and we explore the right part.

149
00:07:27,580 --> 00:07:28,480
So that is how we proceed.

150
00:07:28,480 --> 00:07:29,050
Right now.

151
00:07:29,050 --> 00:07:32,800
We know continuing to explore means nothing but changing the pointer, right?

152
00:07:32,800 --> 00:07:37,750
For example, if we are exploring the left part, all we are doing is we are going to change right to

153
00:07:37,750 --> 00:07:38,830
middle minus one.

154
00:07:38,830 --> 00:07:41,800
And then we have the left pointer over here and the right pointer over here.

155
00:07:41,800 --> 00:07:44,260
So that is what we mean with explore left part.

156
00:07:44,290 --> 00:07:48,130
Now if you want to explore the right part all we are going to do is we are going to change the left

157
00:07:48,130 --> 00:07:52,780
index to the left pointer to this part over here that is middle plus one.

158
00:07:52,780 --> 00:07:54,310
And then right is still over here.

159
00:07:54,310 --> 00:07:56,650
So that is what we mean with explore right part.

160
00:07:56,650 --> 00:08:00,670
Similarly let's say we find that actually the right part is sorted.

161
00:08:00,670 --> 00:08:02,740
So this means right part is sorted.

162
00:08:02,740 --> 00:08:03,130
Again.

163
00:08:03,130 --> 00:08:08,680
If the right part is sorted we are going to decide should I eliminate the right part or should I explore

164
00:08:08,680 --> 00:08:09,280
the right part.

165
00:08:09,280 --> 00:08:10,600
So that is what we are going to check.

166
00:08:10,600 --> 00:08:13,930
Now we are checking whether target is in between these two values.

167
00:08:13,930 --> 00:08:19,120
If it is in between these two values, we will explore the right part, which is we mean we are going

168
00:08:19,120 --> 00:08:20,770
to change left to middle plus one.

169
00:08:20,770 --> 00:08:23,140
So left is coming over here, right is over here.

170
00:08:23,140 --> 00:08:25,390
And we continue we find the middle again.

171
00:08:25,390 --> 00:08:28,600
We continue with this pseudocode over here or the algorithm.

172
00:08:28,600 --> 00:08:35,020
Now if we see that the target value is not between middle and the value at the right index, then we

173
00:08:35,020 --> 00:08:38,380
are going to eliminate the right part and explore the left part.

174
00:08:38,380 --> 00:08:40,270
So explore the left part means nothing.

175
00:08:40,270 --> 00:08:43,930
But we are going to shift right to middle minus one which is over here.

176
00:08:43,930 --> 00:08:45,250
And then we have left over here.

177
00:08:45,250 --> 00:08:48,070
And we continue with the normal binary search algorithm.

178
00:08:48,070 --> 00:08:54,400
So this is the modified binary search algorithm, which we will use to find whether the target value

179
00:08:54,400 --> 00:08:56,740
is in the array which is given to us.

180
00:08:56,740 --> 00:09:02,290
And we are going to do it at O of log n time complexity, because you can see that at every step we

181
00:09:02,290 --> 00:09:05,710
are eliminating one part, either the left part or the right part.

182
00:09:05,710 --> 00:09:06,940
So this is how we are doing it, right.

183
00:09:06,940 --> 00:09:08,350
So let me just write that over here.

184
00:09:08,800 --> 00:09:10,780
Over here we know that the left part is sorted.

185
00:09:10,780 --> 00:09:15,520
If the left part is sorted and the value is not in the left part, we eliminate the left part.

186
00:09:15,520 --> 00:09:18,340
So you can see we are eliminating the left part right now.

187
00:09:18,340 --> 00:09:21,970
If the value is in the left part, we are eliminating the right part.

188
00:09:21,970 --> 00:09:25,630
So you can see we are eliminating half of the input if the left part is sorted.

189
00:09:25,630 --> 00:09:29,500
Similarly, if the right part is sorted, the value is in between the extremes.

190
00:09:29,500 --> 00:09:33,220
Then we are eliminating the left part or exploring the right part.

191
00:09:33,220 --> 00:09:38,680
And if that is not the case, then we explore the left part and we are eliminating the right part.

192
00:09:38,830 --> 00:09:39,190
All right.

193
00:09:39,190 --> 00:09:40,390
So this is how we proceed.

194
00:09:40,390 --> 00:09:43,510
Now let's walk through the algorithm with an example.

195
00:09:43,510 --> 00:09:46,480
Let's say the target is given to us as three.

196
00:09:46,480 --> 00:09:48,100
And let's say this is the array.

197
00:09:48,100 --> 00:09:48,490
All right.

198
00:09:48,490 --> 00:09:52,450
So you can see that 123456789 is sorted.

199
00:09:52,450 --> 00:09:55,240
So it has been rotated with the pivot five.

200
00:09:55,240 --> 00:09:57,250
So that's why it's looking like this now.

201
00:09:57,250 --> 00:09:59,500
So let's go ahead and write the indices over here.

202
00:09:59,500 --> 00:10:03,910
And our algorithm should identify that three is at index seven.

203
00:10:03,910 --> 00:10:05,650
And it should give back index seven.

204
00:10:05,650 --> 00:10:06,490
So that's the question.

205
00:10:06,490 --> 00:10:08,830
So let's proceed and walk through the algorithm.

206
00:10:08,830 --> 00:10:11,230
So we are going to have two pointers left and right.

207
00:10:11,230 --> 00:10:13,060
So left is pointing to index zero.

208
00:10:13,060 --> 00:10:16,630
And right is pointing to the right most index which is eight.

209
00:10:16,630 --> 00:10:22,210
So we go ahead and calculate the middle index which is floor of zero plus eight by two which is equal

210
00:10:22,210 --> 00:10:22,630
to four.

211
00:10:22,630 --> 00:10:25,300
So we have middle at index four which is over here.

212
00:10:25,870 --> 00:10:31,120
Now we are going to check whether the value at the index middle is equal to the target.

213
00:10:31,120 --> 00:10:33,040
We see that they are not equal right.

214
00:10:33,040 --> 00:10:34,720
So nine is not equal to three.

215
00:10:35,110 --> 00:10:35,980
So we proceed.

216
00:10:35,980 --> 00:10:38,620
So we we we cannot return the index at this point.

217
00:10:38,620 --> 00:10:44,050
Now we are going to check is the left part sorted or is the right part sorted.

218
00:10:44,050 --> 00:10:44,980
So that's the next step.

219
00:10:44,980 --> 00:10:50,440
So for this we are going to compare the value at the left index and the value at the middle index.

220
00:10:50,440 --> 00:10:52,780
We see that five is less than nine.

221
00:10:52,780 --> 00:10:56,140
So therefore we know that the left part is sorted right.

222
00:10:56,140 --> 00:10:57,550
So the left part is sorted.

223
00:10:57,550 --> 00:10:59,830
And you can see that it's actually sorted over here.

224
00:10:59,830 --> 00:11:06,130
So after having established this we have to decide should I explore the left side or should I eliminate

225
00:11:06,130 --> 00:11:06,880
the left side.

226
00:11:06,880 --> 00:11:11,560
For this we are going to check whether target is in between 5 and 9.

227
00:11:11,560 --> 00:11:13,360
So is is that the case.

228
00:11:13,840 --> 00:11:15,820
We see that no it's not the case right.

229
00:11:15,820 --> 00:11:18,310
So target is not between 5 and 9.

230
00:11:18,310 --> 00:11:23,110
So that means target cannot be anywhere over here as well because this part is sorted right.

231
00:11:23,110 --> 00:11:28,810
So we are going to explore the right part and we have eliminated the left part.

232
00:11:28,810 --> 00:11:30,250
So this has been eliminated.

233
00:11:30,250 --> 00:11:34,210
So that's why the time complexity of this solution is going to be o of log n.

234
00:11:34,210 --> 00:11:37,450
Because at every step we are eliminating almost half of the input.

235
00:11:37,450 --> 00:11:38,380
So let's proceed.

236
00:11:38,380 --> 00:11:41,710
So we have eliminated the half right eliminated the left half.

237
00:11:41,710 --> 00:11:42,820
And we proceed.

238
00:11:42,820 --> 00:11:45,670
We are going to explore the right part which means that.

239
00:11:45,790 --> 00:11:48,730
You are going to shift the left index to middle plus one.

240
00:11:48,730 --> 00:11:50,320
So we get this two over here.

241
00:11:50,320 --> 00:11:52,030
So we have the left index over here.

242
00:11:52,030 --> 00:11:56,080
And then we're going to calculate the middle which is left plus right divided by two.

243
00:11:56,080 --> 00:11:59,530
And then we're going to take the floor which is five plus eight by two.

244
00:11:59,530 --> 00:12:01,960
And then flooring it which is equal to six.

245
00:12:01,960 --> 00:12:02,230
Right.

246
00:12:02,230 --> 00:12:05,860
So the middle is going to point at index six which is over here.

247
00:12:05,860 --> 00:12:11,260
Again we're going to check whether the target value is equal to the value at the middle index.

248
00:12:11,260 --> 00:12:12,610
We see they are not equal.

249
00:12:12,610 --> 00:12:13,960
So two is not equal to three.

250
00:12:13,960 --> 00:12:14,920
So we proceed.

251
00:12:14,920 --> 00:12:15,370
All right.

252
00:12:15,370 --> 00:12:20,620
Now again we're going to check and compare the value at the left index and the middle index.

253
00:12:20,620 --> 00:12:22,270
So we have one less than two.

254
00:12:22,300 --> 00:12:24,190
So the left part is sorted.

255
00:12:24,190 --> 00:12:26,140
So we know that the left part is sorted.

256
00:12:26,140 --> 00:12:31,660
Now we have to go and decide should I explore the left part or should I eliminate the left part.

257
00:12:31,660 --> 00:12:36,490
For this we are going to check is this value three in between 1 and 2?

258
00:12:36,520 --> 00:12:38,650
Is one less than equal to three less than two?

259
00:12:38,680 --> 00:12:39,550
Is that true?

260
00:12:39,550 --> 00:12:40,480
No, it's not true.

261
00:12:40,480 --> 00:12:40,810
Right.

262
00:12:40,810 --> 00:12:42,400
So this is not true.

263
00:12:42,400 --> 00:12:48,100
That means we have to explore the right part or we have just eliminated the left part.

264
00:12:48,100 --> 00:12:50,650
So you can see the left part has been eliminated.

265
00:12:50,650 --> 00:12:52,450
And we're going to explore the right part.

266
00:12:52,450 --> 00:12:56,440
That is we're going to move the left pointer to middle plus one.

267
00:12:56,440 --> 00:12:59,830
So half has been eliminated again at this step over here.

268
00:13:00,340 --> 00:13:04,990
So the left is pointing at index seven and the right is pointing at index eight.

269
00:13:04,990 --> 00:13:09,460
Again we go ahead and calculate the middle which is floor of seven plus eight by two which is equal

270
00:13:09,460 --> 00:13:10,000
to seven.

271
00:13:10,000 --> 00:13:13,540
So the middle is going to point at index seven at this point.

272
00:13:13,540 --> 00:13:17,920
And you can see that the value over here is equal to three and the target is equal to three.

273
00:13:17,920 --> 00:13:18,880
So these are equal.

274
00:13:18,880 --> 00:13:20,590
So we have found the target.

275
00:13:20,590 --> 00:13:23,140
And we can just return the index seven.

276
00:13:23,140 --> 00:13:27,370
So we will return seven which is the index which is the middle index at this point.

277
00:13:27,370 --> 00:13:29,650
So this is how we are going to solve this question.

278
00:13:29,650 --> 00:13:30,010
All right.

279
00:13:30,010 --> 00:13:32,830
So you can see it's very much similar to the binary search.

280
00:13:32,830 --> 00:13:35,590
The only thing is we have a few extra operations.

281
00:13:35,590 --> 00:13:40,450
Once we find the middle value again we are going to check is the target equal to the value at the middle

282
00:13:40,450 --> 00:13:40,870
index.

283
00:13:40,870 --> 00:13:43,540
Which is the same thing that we did in the case of binary search.

284
00:13:43,540 --> 00:13:50,710
But if it is not equal, then we have to first check is the left part sorted or is the right part sorted?

285
00:13:50,710 --> 00:13:55,810
Now if the left part is sorted, we are going to check is the value in the range of the left part.

286
00:13:55,810 --> 00:13:58,150
If yes, we will explore the left part.

287
00:13:58,150 --> 00:14:01,960
If no, we will explore the right part and eliminate the left part right.

288
00:14:01,960 --> 00:14:04,990
And then if the right part is sorted, we are again going to check.

289
00:14:04,990 --> 00:14:08,890
The same thing is the target value between the extremes of the right part.

290
00:14:08,890 --> 00:14:10,930
If yes, we will explore the right part.

291
00:14:10,930 --> 00:14:15,190
If no, we will eliminate the right part and explore the left part.

292
00:14:15,190 --> 00:14:17,860
So this is how we are going to solve this question.

293
00:14:17,860 --> 00:14:22,060
And you can see that the time complexity is O of log n.

294
00:14:22,060 --> 00:14:23,830
So we have taken an example.

295
00:14:23,830 --> 00:14:26,980
Let's take one more example just to be more clear.

296
00:14:26,980 --> 00:14:27,340
All right.

297
00:14:27,340 --> 00:14:31,060
So we have taken an example where we always went to the right part right.

298
00:14:31,060 --> 00:14:33,160
So let's take an example over here for example.

299
00:14:33,160 --> 00:14:34,420
Again we have the same array.

300
00:14:34,420 --> 00:14:35,770
And the middle is four.

301
00:14:35,770 --> 00:14:37,600
And let's say that the target is six.

302
00:14:37,600 --> 00:14:40,000
So let's see an example where we move to the left.

303
00:14:40,000 --> 00:14:42,550
So over here we see we have five we have nine.

304
00:14:42,550 --> 00:14:45,190
We know that the left part is sorted.

305
00:14:45,190 --> 00:14:49,210
So five less than or equal to this six over here and less than nine.

306
00:14:49,210 --> 00:14:50,110
So this is true.

307
00:14:50,110 --> 00:14:51,310
So what do we do.

308
00:14:51,310 --> 00:14:53,770
We are just going to explore the left part.

309
00:14:53,800 --> 00:14:56,080
Now this is just going to be binary search now.

310
00:14:56,080 --> 00:14:56,380
Right.

311
00:14:56,380 --> 00:15:00,490
Because we are going to look for a target value in a sorted array.

312
00:15:00,490 --> 00:15:02,440
So this part over here is just sorted.

313
00:15:02,440 --> 00:15:04,720
So this is nothing but binary search right.

314
00:15:04,720 --> 00:15:07,480
So we have eliminated the right part in this case.

315
00:15:07,480 --> 00:15:10,090
And then we move the right index over here.

316
00:15:10,090 --> 00:15:12,040
And then this is nothing but binary search.

317
00:15:12,040 --> 00:15:13,750
So we are just going to check again.

318
00:15:13,750 --> 00:15:16,990
We are going to find the middle value which is zero plus three by two.

319
00:15:16,990 --> 00:15:17,980
And then flooring it.

320
00:15:17,980 --> 00:15:18,820
So we'll get one.

321
00:15:18,820 --> 00:15:22,720
And then the middle value the middle index is pointing at one.

322
00:15:22,720 --> 00:15:24,250
And the value over here is six.

323
00:15:24,250 --> 00:15:26,320
And the target value is also equal to six.

324
00:15:26,320 --> 00:15:27,640
And we have found the index.

325
00:15:27,640 --> 00:15:29,260
So which is nothing but binary search.

326
00:15:29,260 --> 00:15:34,780
So you can see that this logic over here, this algorithm over here which we have just now discussed,

327
00:15:34,780 --> 00:15:37,660
runs in O of log n time complexity.

328
00:15:37,660 --> 00:15:42,250
Because at every step we are eliminating half of the input.

329
00:15:42,250 --> 00:15:42,520
Right.

330
00:15:42,520 --> 00:15:47,830
So that is why this solution or this algorithm runs in O of log n, right.

331
00:15:47,830 --> 00:15:50,320
We are eliminating half at every step.

332
00:15:50,350 --> 00:15:55,480
Now the space complexity again is going to be O of log n if you implement it recursively.

333
00:15:55,840 --> 00:16:00,910
And that's going to be pretty much similar to the implementation of binary search recursively, which

334
00:16:00,910 --> 00:16:01,570
you have discussed.

335
00:16:01,570 --> 00:16:06,550
And the space complexity is going to be O of one if you implement this iteratively.

336
00:16:06,550 --> 00:16:09,550
Now in this section we will implement this iteratively.

337
00:16:09,550 --> 00:16:12,700
So let's go ahead and take a look at how we can code this out.