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

2
00:00:01,600 --> 00:00:07,330
Let's now go ahead and write the function which we just now discussed to search in a rotated sorted

3
00:00:07,330 --> 00:00:07,690
array.

4
00:00:07,690 --> 00:00:10,090
So we can call this function search.

5
00:00:11,250 --> 00:00:13,410
Rotated sorted array.

6
00:00:16,350 --> 00:00:16,890
All right.

7
00:00:16,890 --> 00:00:19,890
Now this function is going to take in the array.

8
00:00:19,890 --> 00:00:24,120
So we can call this numb's and the target value which is target.

9
00:00:25,970 --> 00:00:26,330
All right.

10
00:00:26,330 --> 00:00:30,170
Now you can write this function either iteratively or recursively.

11
00:00:30,200 --> 00:00:32,990
Now we will go ahead and write it iteratively.

12
00:00:32,990 --> 00:00:35,120
Now the recursive function is going to be very same.

13
00:00:35,120 --> 00:00:40,070
Very much similar to the recursive implementation of the binary search which we have already discussed

14
00:00:40,070 --> 00:00:41,030
in a previous video.

15
00:00:41,030 --> 00:00:43,640
So let's go ahead and implement this over here iteratively.

16
00:00:43,640 --> 00:00:45,830
So initially we have left at zero.

17
00:00:45,830 --> 00:00:47,390
So we have these two pointers.

18
00:00:47,390 --> 00:00:49,340
So left is pointing to zero.

19
00:00:49,340 --> 00:00:54,830
And right is going to point at the right most index which is numb's dot length minus one.

20
00:00:57,840 --> 00:00:58,170
All right.

21
00:00:58,170 --> 00:01:01,800
Now we'll just have the initialization of the variable middle.

22
00:01:01,800 --> 00:01:07,110
And then we'll have our while loop, which is very much similar to the iterative implementation of the

23
00:01:07,110 --> 00:01:07,980
binary search.

24
00:01:07,980 --> 00:01:12,960
And this is going to go on looping as long as left is less than equal to right.

25
00:01:12,960 --> 00:01:18,270
And we will either break out of this when this is not true, or inside this when we have identified,

26
00:01:18,270 --> 00:01:21,180
when we have located the target value, we can come out.

27
00:01:21,180 --> 00:01:21,570
All right.

28
00:01:21,570 --> 00:01:22,590
So let's proceed.

29
00:01:23,130 --> 00:01:25,410
Now if left is less than equal to right.

30
00:01:25,410 --> 00:01:26,850
First we will calculate middle.

31
00:01:26,850 --> 00:01:29,430
So middle is going to be math dot floor.

32
00:01:30,570 --> 00:01:34,230
And we have left plus right divided by two.

33
00:01:39,310 --> 00:01:39,670
All right.

34
00:01:39,670 --> 00:01:41,020
So we have the middle index.

35
00:01:41,020 --> 00:01:46,420
Now we are going to check whether target is equal to the value in the array at the middle index.

36
00:01:46,420 --> 00:01:48,910
So if target is equal to numb's at middle.

37
00:01:48,910 --> 00:01:54,190
So if this is the case then we can just return middle and we are out or.

38
00:01:54,190 --> 00:01:54,490
All right.

39
00:01:54,490 --> 00:01:56,710
So this is part of the call of this function.

40
00:01:56,710 --> 00:01:57,640
So we are returning.

41
00:01:57,640 --> 00:01:59,260
And then we'll be out of this function.

42
00:01:59,260 --> 00:02:02,110
Now if this is not equal then we proceed.

43
00:02:02,110 --> 00:02:07,240
So first we have to identify whether the left part or the right part is sorted.

44
00:02:07,240 --> 00:02:08,200
So let's do that.

45
00:02:08,200 --> 00:02:16,930
So if numb's at left if numb's at left is going to be less than or equal to the middle value that is

46
00:02:16,930 --> 00:02:18,160
numb's at middle.

47
00:02:18,980 --> 00:02:22,340
Then we know that the left part is sorted right?

48
00:02:22,340 --> 00:02:24,410
So we know that left is sorted.

49
00:02:27,100 --> 00:02:32,110
Now, if this is not the case, so else we know that right is sorted.

50
00:02:33,510 --> 00:02:33,900
All right.

51
00:02:33,900 --> 00:02:37,920
Now we need to know whether we should look in the left part or the right part.

52
00:02:37,920 --> 00:02:42,210
So for this, we have to see whether the target value is in which range.

53
00:02:42,210 --> 00:02:43,110
So let's proceed.

54
00:02:43,110 --> 00:02:44,820
So let's say left is sorted.

55
00:02:44,820 --> 00:02:52,110
Now in that case we have to check if target is greater than equal to numb's at left.

56
00:02:53,840 --> 00:02:54,680
And.

57
00:02:55,330 --> 00:02:59,980
Target is less than numb's at middle right.

58
00:02:59,980 --> 00:03:03,280
So this means that if this is true then target is in.

59
00:03:03,280 --> 00:03:04,960
That part is in the left part right.

60
00:03:04,960 --> 00:03:07,750
So that means we can explore the left part.

61
00:03:09,460 --> 00:03:09,820
All right.

62
00:03:09,820 --> 00:03:11,110
So what does this mean?

63
00:03:11,110 --> 00:03:15,340
This means left is sorted and target is within the bounds of the left part.

64
00:03:15,340 --> 00:03:20,530
So we can just explore the left part to see whether target is present in the array which is given to

65
00:03:20,530 --> 00:03:20,860
us.

66
00:03:20,860 --> 00:03:22,450
Now if this is not the case.

67
00:03:22,450 --> 00:03:28,570
So if else we know that the left is still sorted, but we also know that target is not in the left part,

68
00:03:28,570 --> 00:03:31,090
so we can just explore the right part.

69
00:03:34,440 --> 00:03:36,420
All right, now, let's proceed.

70
00:03:36,420 --> 00:03:39,360
Now, let's also just go ahead and write the other possibilities.

71
00:03:39,360 --> 00:03:42,180
So over here else means the right is sorted.

72
00:03:42,180 --> 00:03:47,190
Now if the right part is sorted again we're going to check if target is in that range.

73
00:03:47,190 --> 00:03:51,810
So if target is less than equal to numb's.

74
00:03:53,550 --> 00:03:53,760
At.

75
00:03:53,760 --> 00:03:54,360
Right?

76
00:03:54,690 --> 00:03:55,260
Right.

77
00:03:55,260 --> 00:04:00,330
And if target is greater than numb's at middle.

78
00:04:05,820 --> 00:04:08,040
We know that target is in this range, right.

79
00:04:08,040 --> 00:04:11,550
So in that case we can explore the right part.

80
00:04:12,090 --> 00:04:14,070
So again let's repeat what is happening over here.

81
00:04:14,070 --> 00:04:15,510
So we are in this else part.

82
00:04:15,510 --> 00:04:18,210
That means the right part is sorted.

83
00:04:18,210 --> 00:04:20,610
And if this is true then target.

84
00:04:20,610 --> 00:04:23,580
The value of target is in the range of the right part.

85
00:04:23,580 --> 00:04:25,140
So we can explore the right part.

86
00:04:25,170 --> 00:04:30,720
Now if this is an if this is not true, that is the right part is still sorted but target is not in

87
00:04:30,720 --> 00:04:34,350
this range, then we will go ahead and explore the left part.

88
00:04:35,810 --> 00:04:36,050
All right.

89
00:04:36,050 --> 00:04:37,850
So this is how we're going to implement this.

90
00:04:37,850 --> 00:04:38,720
Let's again repeat.

91
00:04:38,720 --> 00:04:39,590
What are we doing.

92
00:04:39,590 --> 00:04:44,060
We are first we are trying to identify whether the left part or the right part is sorted.

93
00:04:44,060 --> 00:04:46,130
Now let's say the left part is sorted.

94
00:04:46,130 --> 00:04:50,750
If that is the case we are going ahead and checking whether target is in the range of the values in

95
00:04:50,750 --> 00:04:51,440
the left part.

96
00:04:51,440 --> 00:04:55,160
If that is true, then we can only find target in the left part.

97
00:04:55,160 --> 00:05:00,770
If that is not true, even though the left part is sorted, but because the target value is not there

98
00:05:00,770 --> 00:05:03,440
in that range, we're going to explore the right part.

99
00:05:03,440 --> 00:05:08,480
So you can see that in either of these cases, we are eliminating half of the input at every step.

100
00:05:08,480 --> 00:05:11,210
And that's why this is a o of log n operation.

101
00:05:11,210 --> 00:05:11,630
Right.

102
00:05:12,080 --> 00:05:14,360
So let's go ahead and complete the function.

103
00:05:14,360 --> 00:05:16,340
So let's say the left part is sorted.

104
00:05:16,340 --> 00:05:19,070
And let's say the target value is in this range.

105
00:05:19,070 --> 00:05:20,870
Then what we what do we do.

106
00:05:20,870 --> 00:05:22,670
We go ahead and explore the left part.

107
00:05:22,700 --> 00:05:29,030
Now exploring the left part means we are going to eliminate the right part, which is making right equal

108
00:05:29,030 --> 00:05:30,860
to middle minus one.

109
00:05:31,130 --> 00:05:31,490
All right.

110
00:05:31,490 --> 00:05:34,040
So this is the same thing what we did in binary search.

111
00:05:34,040 --> 00:05:39,290
If you wanted to only explore explore the left part we did right is equal to middle minus one.

112
00:05:39,290 --> 00:05:41,300
So that's the same thing what we are doing over here.

113
00:05:41,300 --> 00:05:46,130
Now if we are over here if you want to explore the right part again, what what are we going to do.

114
00:05:46,130 --> 00:05:48,800
We're just making left equal to middle plus one.

115
00:05:48,800 --> 00:05:51,440
So this is the same thing that we did in the binary search.

116
00:05:51,440 --> 00:05:51,890
All right.

117
00:05:51,890 --> 00:05:55,340
So let's proceed now over here also the same thing.

118
00:05:55,340 --> 00:06:00,680
We have decided that we have to explore the right part, which means that we will just say left is equal

119
00:06:00,680 --> 00:06:02,270
to middle plus one.

120
00:06:02,870 --> 00:06:09,350
And over here if we want to explore the left part we will say right is equal to middle minus one.

121
00:06:10,410 --> 00:06:10,680
All right.

122
00:06:10,680 --> 00:06:12,360
So that's the end of our function.

123
00:06:12,360 --> 00:06:18,120
Now if we are out of the while loop over here and we have not yet returned anything, then we will just

124
00:06:18,120 --> 00:06:23,490
return minus one, which means that the particular target value is not there in the array which we are

125
00:06:23,490 --> 00:06:24,000
searching.

126
00:06:24,000 --> 00:06:24,390
All right.

127
00:06:24,390 --> 00:06:26,910
So let's go ahead and try to run this function.

128
00:06:26,910 --> 00:06:29,160
And let's test our code first.

129
00:06:29,430 --> 00:06:30,990
So I'm calling the function over here.

130
00:06:30,990 --> 00:06:34,800
Now initially let me just pass in a simple array 12345.

131
00:06:34,800 --> 00:06:37,500
And let's say we are searching for the value one.

132
00:06:37,980 --> 00:06:40,020
So let's try to run our code.

133
00:06:41,090 --> 00:06:43,250
You can see we are getting zero, which is correct.

134
00:06:43,250 --> 00:06:44,360
So one is at index zero.

135
00:06:44,360 --> 00:06:45,020
That's correct.

136
00:06:45,050 --> 00:06:47,570
Now what if I run this with five.

137
00:06:47,870 --> 00:06:48,860
Yes, I get four.

138
00:06:48,890 --> 00:06:49,550
That's correct.

139
00:06:49,550 --> 00:06:52,340
Now let's say that this array has been rotated one time.

140
00:06:52,340 --> 00:06:55,310
So it would be 5123 and four right.

141
00:06:55,310 --> 00:06:57,650
So let's say we are again searching for five.

142
00:06:57,650 --> 00:06:59,750
And we are getting the index zero which is correct.

143
00:06:59,750 --> 00:07:01,850
Let's say we are searching for three.

144
00:07:02,810 --> 00:07:05,870
And we are getting the index three zero, one, two and three.

145
00:07:05,870 --> 00:07:06,800
So this is at three.

146
00:07:06,800 --> 00:07:08,240
So this is also correct.

147
00:07:08,240 --> 00:07:08,630
All right.

148
00:07:08,630 --> 00:07:09,830
So our function is working.

149
00:07:09,830 --> 00:07:11,540
So let's again do one more rotation.

150
00:07:11,540 --> 00:07:14,240
So let's say we have 45123.

151
00:07:14,240 --> 00:07:16,550
And let's say we are searching for again three.

152
00:07:16,550 --> 00:07:18,470
So we are getting four which is correct.

153
00:07:18,470 --> 00:07:19,850
So this is at index four.

154
00:07:19,850 --> 00:07:23,870
Let's say we are searching for four over here and we are getting zero.

155
00:07:23,870 --> 00:07:24,860
That's also correct.

156
00:07:24,860 --> 00:07:29,630
And let's say we are searching for five over here and we're getting index one which is also correct.

157
00:07:29,630 --> 00:07:30,770
So our function is working.

158
00:07:30,770 --> 00:07:34,700
Now let's take this example and let's just walk through the code and see what's happening.

159
00:07:35,180 --> 00:07:35,630
All right.

160
00:07:35,630 --> 00:07:39,830
So we are having this array over here 45123.

161
00:07:39,830 --> 00:07:42,020
And let's say the target value is equal to five.

162
00:07:42,020 --> 00:07:43,670
So let me just write this over here.

163
00:07:43,670 --> 00:07:47,840
So we have 4512 and three.

164
00:07:47,840 --> 00:07:50,540
And the target value is equal to five.

165
00:07:50,540 --> 00:07:52,160
That's what we are searching for.

166
00:07:52,160 --> 00:07:53,120
So let's proceed.

167
00:07:53,120 --> 00:07:56,480
So we call search rotated sorted array function.

168
00:07:56,480 --> 00:07:57,830
And this array over here is passed.

169
00:07:57,830 --> 00:07:59,480
And the target value is equal to five.

170
00:07:59,480 --> 00:08:01,940
Now initially left is going to be equal to zero.

171
00:08:01,940 --> 00:08:07,670
So this is left and right is going to be numb's dot length which is five minus one which is four.

172
00:08:07,670 --> 00:08:10,610
So over here right is going to point at index four.

173
00:08:10,610 --> 00:08:11,960
And then we have middle.

174
00:08:11,960 --> 00:08:14,150
Now zero is less than four.

175
00:08:14,150 --> 00:08:17,840
So that's truthy this while loop over here this condition is truthy.

176
00:08:17,840 --> 00:08:19,520
So we come inside the while loop.

177
00:08:20,090 --> 00:08:20,540
All right.

178
00:08:20,570 --> 00:08:24,170
Now we find the middle value which is zero plus four divided by two which is two.

179
00:08:24,200 --> 00:08:26,330
So middle is pointing to at index two.

180
00:08:26,360 --> 00:08:30,350
Now we are checking whether five is equal to the value at middle which is one.

181
00:08:30,350 --> 00:08:31,610
So that's not the case.

182
00:08:31,610 --> 00:08:32,660
So we proceed.

183
00:08:32,660 --> 00:08:36,830
Now we are going to check whether numb's at left which is this four over here.

184
00:08:36,830 --> 00:08:39,860
Is it less than equal to numb's at middle which is one.

185
00:08:39,860 --> 00:08:41,180
That's not the case.

186
00:08:41,180 --> 00:08:44,180
So we know that the left is not sorted right.

187
00:08:44,180 --> 00:08:45,560
So this is not the case.

188
00:08:45,560 --> 00:08:49,640
So we come to this part and we know that the right is sorted which is the truth.

189
00:08:49,640 --> 00:08:49,940
Right.

190
00:08:49,940 --> 00:08:52,460
So over here you can see the right part over here is sorted.

191
00:08:52,460 --> 00:08:52,880
Right.

192
00:08:52,880 --> 00:08:53,930
So we proceed.

193
00:08:54,760 --> 00:09:00,580
Now because the right is sorted, we come over here and now we are going to check whether target, which

194
00:09:00,580 --> 00:09:02,170
is five, is in this range.

195
00:09:02,170 --> 00:09:05,320
So is target less than equal to numb's at right.

196
00:09:05,320 --> 00:09:07,300
So this is three this is five right.

197
00:09:07,300 --> 00:09:08,890
Five is not less than three right.

198
00:09:08,890 --> 00:09:12,520
So we know that the target value is not in this range.

199
00:09:12,520 --> 00:09:14,080
Now what is it that we know.

200
00:09:14,080 --> 00:09:16,090
We know that the right part is sorted.

201
00:09:16,480 --> 00:09:17,350
We know that.

202
00:09:17,350 --> 00:09:20,620
And we know that target is not in this range.

203
00:09:20,620 --> 00:09:25,180
So we know that target is not in this range by just comparing the two extremes.

204
00:09:25,180 --> 00:09:30,580
Because this part over here is sorted now because target is not in this part, we can eliminate this

205
00:09:30,580 --> 00:09:30,970
part.

206
00:09:30,970 --> 00:09:34,690
That is, we are saying right is equal to middle minus one.

207
00:09:34,690 --> 00:09:36,550
So we are changing this to over here.

208
00:09:37,520 --> 00:09:39,320
The right is at middle minus one.

209
00:09:39,320 --> 00:09:41,990
So we calculate the new middle right.

210
00:09:41,990 --> 00:09:44,090
So over here left is at zero.

211
00:09:44,090 --> 00:09:44,900
Right is at one.

212
00:09:44,900 --> 00:09:49,310
So middle is equal to zero plus one divided by two which is 0.5.

213
00:09:49,310 --> 00:09:52,490
And when we flow rate middle is going to be equal to zero.

214
00:09:52,490 --> 00:09:54,470
Again we check are these two equal.

215
00:09:54,470 --> 00:09:56,540
So we come over here zero is less than one.

216
00:09:56,540 --> 00:09:57,440
So yes that's true.

217
00:09:57,590 --> 00:09:59,060
So we come inside the while loop.

218
00:09:59,060 --> 00:10:01,550
And we are going to calculate middle which is zero.

219
00:10:01,550 --> 00:10:02,720
Now zero.

220
00:10:02,720 --> 00:10:04,850
This this value over here is four and this is five.

221
00:10:04,850 --> 00:10:05,900
So they are not equal.

222
00:10:05,900 --> 00:10:07,490
So we don't go ahead with this.

223
00:10:07,520 --> 00:10:08,360
We come over here.

224
00:10:08,360 --> 00:10:11,810
Now we are checking whether Numb's had left which which is four.

225
00:10:11,810 --> 00:10:14,840
Is it less than or equal to Numb's at middle which is also four.

226
00:10:14,870 --> 00:10:15,890
That's true right.

227
00:10:15,890 --> 00:10:16,640
That's true.

228
00:10:16,640 --> 00:10:18,740
So we know that the left part is sorted.

229
00:10:18,740 --> 00:10:19,220
Right.

230
00:10:19,610 --> 00:10:21,860
And again there's nothing else over here.

231
00:10:21,860 --> 00:10:26,240
So the left also is pointing to the same index where middle is pointing at.

232
00:10:26,240 --> 00:10:30,200
So over here we check whether target is greater than equal to numb's at left.

233
00:10:30,200 --> 00:10:32,270
So we know that five is greater than this four.

234
00:10:32,270 --> 00:10:37,250
So that's truthy and is target less than numb's at middle is five less than four.

235
00:10:37,250 --> 00:10:37,820
That's false.

236
00:10:38,030 --> 00:10:39,740
So we don't go ahead with this.

237
00:10:39,740 --> 00:10:40,790
So we come over here.

238
00:10:40,790 --> 00:10:43,430
That means we're going to explore the right part.

239
00:10:43,430 --> 00:10:45,860
So the right part over here is only this value.

240
00:10:45,860 --> 00:10:46,250
Right.

241
00:10:46,250 --> 00:10:47,600
We just have this one left.

242
00:10:47,600 --> 00:10:50,000
So we're going to say left is equal to middle plus one.

243
00:10:50,000 --> 00:10:52,280
So left is also going to point over here.

244
00:10:52,280 --> 00:10:55,790
And right and left are pointing at the same index.

245
00:10:55,790 --> 00:10:59,690
And then middle is also going to be equal to one right in the next.

246
00:10:59,690 --> 00:11:01,940
In the next loop we have one less than equal to one.

247
00:11:01,940 --> 00:11:02,540
That's true.

248
00:11:02,660 --> 00:11:03,620
So we come inside.

249
00:11:03,620 --> 00:11:07,010
Middle is going to be equal to one plus one divided by two which is one.

250
00:11:07,010 --> 00:11:10,160
And we see that five is equal to the value at index one.

251
00:11:10,160 --> 00:11:13,010
So we are going to return this index which is one.

252
00:11:13,010 --> 00:11:14,690
So that's how our function works.

253
00:11:14,690 --> 00:11:19,580
Now we can see that at every step we are eliminating half of the input.

254
00:11:19,580 --> 00:11:25,070
So that's why the time complexity of this solution is going to be the same as the time complexity of

255
00:11:25,070 --> 00:11:28,340
the binary search which is equal to O of log n, right.

256
00:11:28,340 --> 00:11:31,490
So the time complexity over here is equal to O of log n.

257
00:11:32,820 --> 00:11:38,730
And the space complexity is equal to O of one, because this implementation is the iterative implementation

258
00:11:38,730 --> 00:11:41,040
and we are not using any auxiliary space.

259
00:11:41,070 --> 00:11:46,350
Now again, just to repeat, let's see how we are eliminating the half of the input at every step.

260
00:11:46,350 --> 00:11:50,070
So first we are checking if the target is equal to middle.

261
00:11:50,070 --> 00:11:52,560
So this is the same as the case of the binary search.

262
00:11:52,560 --> 00:11:56,100
Now if that is not the case we have a few extra steps.

263
00:11:56,100 --> 00:12:00,690
We have to first identify whether the left part or the right part is sorted.

264
00:12:00,690 --> 00:12:05,520
Right now, if Numb's had left less than equal to numb's at middle, we know that the left part is sorted,

265
00:12:05,520 --> 00:12:07,680
else we know that the right part is sorted.

266
00:12:07,680 --> 00:12:11,100
So either the left part or the right part is going to be sorted.

267
00:12:11,100 --> 00:12:16,650
Now, if the left part is sorted, we are just going to check the extremities of the left part, which

268
00:12:16,650 --> 00:12:18,960
is numb's at left and numb's at middle.

269
00:12:18,960 --> 00:12:22,170
Now we will check whether target is between these two values.

270
00:12:22,170 --> 00:12:27,810
If that is the case, then we know that target can only be in the left part and we can eliminate the

271
00:12:27,810 --> 00:12:28,260
right part.

272
00:12:28,260 --> 00:12:31,080
So over here we are eliminating the right part.

273
00:12:31,080 --> 00:12:31,620
All right.

274
00:12:32,100 --> 00:12:38,520
Now if the left part is sorted and the target is not in the range of the left part, then we know that

275
00:12:38,520 --> 00:12:40,590
it can only be there in the right part.

276
00:12:40,590 --> 00:12:43,200
So in this case we are going to eliminate the left part.

277
00:12:43,200 --> 00:12:47,280
So you can see that in either case we are eliminating half of the remaining input.

278
00:12:47,280 --> 00:12:47,730
Right.

279
00:12:47,730 --> 00:12:52,980
And in this case if the right is sorted again we are checking if target is in the range of the right

280
00:12:52,980 --> 00:12:57,360
by checking its extremities, which is numb's at right and numb's at middle.

281
00:12:57,360 --> 00:13:02,070
Now if target is in between this, we know that it can only be in the right part.

282
00:13:02,070 --> 00:13:04,950
So we are eliminating the left part right now.

283
00:13:04,950 --> 00:13:10,560
If it is not in this range and the right part is sorted and the value is not in the range of the right

284
00:13:10,560 --> 00:13:12,240
part, we can eliminate the right part.

285
00:13:12,240 --> 00:13:14,490
So we are going to only explore the left part.

286
00:13:14,490 --> 00:13:16,710
So over here we are eliminating the right part.

287
00:13:16,710 --> 00:13:21,780
So you can see that either case, whatever be the case we are going to eliminate half of the input at

288
00:13:21,780 --> 00:13:22,410
every step.

289
00:13:22,410 --> 00:13:26,280
And that's why the time complexity of this solution is O of log n.