1
00:00:02,090 --> 00:00:03,690
Hey, guys, what's up?

2
00:00:04,040 --> 00:00:10,760
So in this video, we will learn how to search for a given key in an area.

3
00:00:11,230 --> 00:00:12,730
OK, so what will happen?

4
00:00:13,190 --> 00:00:14,390
We will be given an.

5
00:00:15,440 --> 00:00:23,910
So we have an ETA letter that elements are 10, 20, three, four one zero.

6
00:00:24,440 --> 00:00:30,770
OK, so we have an ETA and let's say we have to search for 20.

7
00:00:31,960 --> 00:00:36,100
OK, so we have to search for a given value in adding.

8
00:00:37,580 --> 00:00:45,200
And we have to tell whether the given value is present or not present, so zero, one, two, three,

9
00:00:45,200 --> 00:00:46,240
four and five.

10
00:00:46,640 --> 00:00:48,050
So these are my indexers.

11
00:00:49,330 --> 00:00:59,710
OK, so, for example, in this case, 20 percent, some output will be one, OK, one means index that

12
00:00:59,710 --> 00:01:02,270
is going days present at index one.

13
00:01:03,310 --> 00:01:09,970
So, for example, if the key that we have to search for is a 30, that is not present.

14
00:01:10,300 --> 00:01:13,360
So Melbourne should be not present.

15
00:01:14,590 --> 00:01:20,470
Or you can say Guinot found Key not found.

16
00:01:21,350 --> 00:01:24,230
And here we have found key.

17
00:01:25,300 --> 00:01:27,100
At position.

18
00:01:29,380 --> 00:01:36,910
One, OK, so user will give us an array and user will give us for the value that we have to search

19
00:01:36,910 --> 00:01:43,820
in the area and if the given key is present in the array, you have to print that.

20
00:01:43,840 --> 00:01:48,070
Yes, the given key is better than that, and it is present at position one.

21
00:01:48,550 --> 00:01:55,330
And if the given key is not present in the area, then your output should be the given keys, not present.

22
00:01:55,840 --> 00:01:58,850
OK, so this is the task that we have to perform.

23
00:01:59,110 --> 00:02:00,670
So how we can solve this problem.

24
00:02:01,430 --> 00:02:04,060
So the algorithm for solving this problem is very simple.

25
00:02:05,110 --> 00:02:06,910
What we will do, we will scan that.

26
00:02:07,660 --> 00:02:11,810
We will scan array from left to right.

27
00:02:12,550 --> 00:02:19,510
OK, so starting from zero to end minus one, we will scan the Eddie, for example, my arrays, let's

28
00:02:19,510 --> 00:02:24,100
say five four two one three zero.

29
00:02:24,520 --> 00:02:29,350
And the value for which we have to search and let's say my key is to.

30
00:02:29,620 --> 00:02:36,250
So what we will do I will check is five for close to know is very close to know.

31
00:02:36,520 --> 00:02:37,500
Is too close to.

32
00:02:37,510 --> 00:02:37,930
Yes.

33
00:02:37,930 --> 00:02:39,340
To be close to stop.

34
00:02:40,690 --> 00:02:48,250
So ultimately, what we are doing, we are getting that from left to right, from zero to index and

35
00:02:48,250 --> 00:02:48,890
minus one.

36
00:02:49,180 --> 00:02:54,850
Similarly, if we have to search for, let's say zero, so it's five equals zero.

37
00:02:54,850 --> 00:02:56,710
No, four equals zero.

38
00:02:56,710 --> 00:02:58,390
No, two equals zero.

39
00:02:58,390 --> 00:03:00,220
No one equals zero.

40
00:03:00,250 --> 00:03:01,960
No, three equals zero.

41
00:03:01,960 --> 00:03:04,230
No, zero equals zero.

42
00:03:04,240 --> 00:03:04,630
Yes.

43
00:03:06,580 --> 00:03:16,690
Key found, key found at position, we found the key position, so zero, one, two, three, four and

44
00:03:16,690 --> 00:03:16,990
five.

45
00:03:17,440 --> 00:03:19,990
So key found at position five.

46
00:03:21,670 --> 00:03:26,050
OK, suppose the given key is, let's say.

47
00:03:27,190 --> 00:03:27,710
Six.

48
00:03:28,090 --> 00:03:37,870
OK, so Jack is five equals six now is for equal six now is two equals six, nor is one equals six.

49
00:03:37,870 --> 00:03:39,610
No ethical six.

50
00:03:39,610 --> 00:03:40,810
No is zero.

51
00:03:40,810 --> 00:03:41,630
Equal six, no.

52
00:03:41,650 --> 00:03:42,640
So I will reach here.

53
00:03:43,490 --> 00:03:45,130
OK, so I will reach our position.

54
00:03:45,130 --> 00:03:48,910
And that means gay sex is not present.

55
00:03:51,470 --> 00:03:54,230
Sex is not present in the Eddie.

56
00:03:56,680 --> 00:04:03,220
So our algorithm is very simple, what we will do, we will scan the area, we will scan the area.

57
00:04:03,800 --> 00:04:05,870
OK, so very simple.

58
00:04:06,820 --> 00:04:08,770
So our court will look something like this.

59
00:04:10,140 --> 00:04:21,269
I will start I will start scanning from zero till the last position and what I will check I will check

60
00:04:21,269 --> 00:04:28,500
if the current value is equal to Gyi that we have to search, then yes.

61
00:04:28,500 --> 00:04:31,800
See found found the key.

62
00:04:33,460 --> 00:04:43,480
Found key and similarly, if the value of A becomes and and may also break here, OK, after we found

63
00:04:43,480 --> 00:04:44,810
the key, we will break.

64
00:04:45,190 --> 00:04:50,470
So if the value of my question, that means this Lopez terminated naturally.

65
00:04:51,730 --> 00:04:53,680
So this will be terminated naturally.

66
00:04:53,680 --> 00:04:55,210
That means the value of five becomes.

67
00:04:55,220 --> 00:04:58,750
And so we can say gey not found.

68
00:04:59,830 --> 00:05:04,600
OK, so we are just doing the linear scan, we are just doing the linear.

69
00:05:04,960 --> 00:05:11,740
And each time I am comparing the value, if I got a match I am printing guess the key found and I'm

70
00:05:11,740 --> 00:05:12,910
breaking the loop.

71
00:05:13,490 --> 00:05:20,710
OK, and if the value of AI becomes and that means the slope is terminated, naturally this big statement

72
00:05:20,710 --> 00:05:25,960
has not been executed and that means the key is not present in the array.

73
00:05:27,190 --> 00:05:28,270
So that as I told.

74
00:05:29,830 --> 00:05:37,600
So I have named this file as linear search NBP, so via name this file as linear search, because I

75
00:05:37,600 --> 00:05:43,190
am searching, I am searching linearly, OK?

76
00:05:43,350 --> 00:05:46,730
So I am doing searching linearly.

77
00:05:46,750 --> 00:05:49,720
So that's why they call it linear search.

78
00:05:50,770 --> 00:05:57,430
OK, so this is called Línea Search, Vilina Search, because I am searching linearly.

79
00:05:58,880 --> 00:06:06,920
So the name of this file is lenience, that's not TBP, so first let us take in and let us take inpart.

80
00:06:09,170 --> 00:06:10,580
Now, let us make any.

81
00:06:13,850 --> 00:06:16,910
Now, let us take the values off at as import.

82
00:06:23,760 --> 00:06:32,900
So what I am writing, I am writing a function and it will give me a position so I have a function,

83
00:06:33,690 --> 00:06:41,030
the name of the function is linear, linear, such OK, so linear search function will take to this

84
00:06:41,160 --> 00:06:42,240
function, will take at it.

85
00:06:42,660 --> 00:06:48,980
And the size of that is input and it will return me the position at which the number is present.

86
00:06:48,990 --> 00:06:51,290
The key is present when thing here.

87
00:06:51,840 --> 00:06:55,380
We also need to take the key for which we have to sort something out.

88
00:06:56,010 --> 00:06:57,150
And the key.

89
00:07:02,210 --> 00:07:06,650
So let us make a variable in key and see in key.

90
00:07:07,850 --> 00:07:14,550
OK, so we also need to pass key here, so, yes, it will take three arguments at the site of that.

91
00:07:14,930 --> 00:07:21,560
And the key for which it will search and what function will return, the search function will return

92
00:07:21,890 --> 00:07:25,310
medy position at which the given key is present.

93
00:07:26,570 --> 00:07:34,010
So let's make the function so they don't end because we will retain the position name of the function

94
00:07:34,010 --> 00:07:34,910
is Leanyer.

95
00:07:37,750 --> 00:07:47,080
Search, and it is taking three arguments as input, so and at the size of the area and the third argument

96
00:07:47,080 --> 00:07:53,110
or the third parameter is the key for which it will do search, it will perform a search operation.

97
00:07:53,890 --> 00:08:01,620
So what I have to do, I have to do just a linear scan of the area so far and I equals zero.

98
00:08:01,630 --> 00:08:10,900
I last and I placeless what I have to do, compare the current value, compare the current value, which

99
00:08:10,900 --> 00:08:13,440
is elfy with the given key.

100
00:08:13,780 --> 00:08:18,420
And if you got a match that means the given key is present in the area.

101
00:08:18,640 --> 00:08:20,260
So you will return.

102
00:08:21,130 --> 00:08:23,140
I guess I will return.

103
00:08:23,140 --> 00:08:24,550
I, I miss.

104
00:08:25,660 --> 00:08:30,850
So what I have to return I have to return the position at which the given case present so that given

105
00:08:30,850 --> 00:08:34,059
his present position, I so I am returning a.

106
00:08:35,250 --> 00:08:44,159
And if this loop got terminated, so if I reach line number 12, that means the given guy is not present

107
00:08:44,159 --> 00:08:47,730
in the ETTY, then I can return.

108
00:08:48,750 --> 00:08:50,850
I can return minus one.

109
00:08:53,120 --> 00:09:00,290
OK, so if the gunky is not present in the area, what will happen, this return written statement will

110
00:09:00,410 --> 00:09:02,120
never be executed.

111
00:09:03,280 --> 00:09:08,590
So if this statement is never executed, this loop will get terminated naturally.

112
00:09:09,750 --> 00:09:16,350
And if this loop gets terminated, naturally, that means the given guy is not present in the area and

113
00:09:16,380 --> 00:09:22,400
I am returning minus one Y minus one because minus one is not a valid index.

114
00:09:22,830 --> 00:09:28,300
You can also written minus 10, minus 20, minus three, minus four, minus five, minus hundred.

115
00:09:28,370 --> 00:09:32,840
OK, so you just have to return an invalid index.

116
00:09:32,850 --> 00:09:35,070
So minus one is an invalid index.

117
00:09:35,280 --> 00:09:36,750
So I'm returning minus one.

118
00:09:38,240 --> 00:09:39,980
So this is the position.

119
00:09:41,030 --> 00:09:52,310
So first of all, I will check if the position so if the operation equals equals minus one, that means

120
00:09:52,640 --> 00:09:55,180
the given key is not present in the eddy.

121
00:09:55,670 --> 00:09:56,900
So you can see out.

122
00:09:59,580 --> 00:10:04,890
Guinot found Gey not found.

123
00:10:06,060 --> 00:10:12,290
OK, as we can safely say that the given key is present.

124
00:10:12,720 --> 00:10:23,400
OK, so setout out key found at index position.

125
00:10:27,100 --> 00:10:28,780
OK, so this is our entire call.

126
00:10:28,900 --> 00:10:29,770
Let's see it again.

127
00:10:30,340 --> 00:10:34,930
So leniencies function is taking three arguments, three barometer's as input.

128
00:10:35,290 --> 00:10:36,940
I am doing a linear scan.

129
00:10:37,150 --> 00:10:40,500
I am comparing the value of G with the current value.

130
00:10:40,780 --> 00:10:48,490
If I got a match, I will return I OK, so this function will return any data that is position at which

131
00:10:48,490 --> 00:10:49,270
the key is found.

132
00:10:49,870 --> 00:10:53,620
And if this loop got terminated, naturally I am returning minus one.

133
00:10:53,620 --> 00:10:56,320
Minus one means are invalid index.

134
00:10:56,560 --> 00:10:58,650
That means key not found.

135
00:10:59,050 --> 00:11:07,360
So it is my position I am taking if position equals minus one key not found otherwise key found at index

136
00:11:07,720 --> 00:11:08,380
position.

137
00:11:10,830 --> 00:11:11,790
So let's compile.

138
00:11:15,570 --> 00:11:17,980
OK, so it will be D'Arte.

139
00:11:22,760 --> 00:11:24,290
OK, it will be set in.

140
00:11:30,070 --> 00:11:31,300
So let's say there are.

141
00:11:32,510 --> 00:11:40,190
Five elements and the elements are one, two, three, four and five, so in Turkey, for example,

142
00:11:40,190 --> 00:11:48,810
I want to search for three so lucky found at next to OK, so this is a net zero and one and next two

143
00:11:48,980 --> 00:11:50,930
to three found at index to.

144
00:11:53,740 --> 00:12:02,850
One more time later, number of elements are four and the elements are five, seven, eight and zero.

145
00:12:04,360 --> 00:12:06,790
So I want to search for zero.

146
00:12:08,050 --> 00:12:10,100
So we found at index three.

147
00:12:10,120 --> 00:12:11,430
So this is our industry.

148
00:12:12,040 --> 00:12:14,500
OK, indexing at a start from zero.

149
00:12:16,200 --> 00:12:17,070
Now, last time.

150
00:12:18,240 --> 00:12:27,450
Suppose MPs are five and the elements are one, two, three, four and five, and I want to search for

151
00:12:27,450 --> 00:12:27,900
six.

152
00:12:29,130 --> 00:12:32,670
So Kinnard found OK, Gey not found.

153
00:12:36,700 --> 00:12:38,710
Now, one last thing that I want to clear.

154
00:12:41,420 --> 00:12:50,810
OK, so, for example, if my is one, two and three and my key is when I guess what will happen, I

155
00:12:50,810 --> 00:12:58,070
close the door, I listen and I placeless aof zero initially vilify zero zero eight klasky.

156
00:12:58,310 --> 00:13:04,600
So one equals one, one equals one return I so I is zero zero one two.

157
00:13:04,940 --> 00:13:06,720
So return I that is return zero.

158
00:13:07,310 --> 00:13:12,800
OK, so as soon as this return statement is executed, this program is finished.

159
00:13:13,690 --> 00:13:20,680
OK, this dysfunction is finished, if this statement is executed, I will directly return the value

160
00:13:21,010 --> 00:13:22,980
and the program will not be executed.

161
00:13:26,110 --> 00:13:26,980
So one more time.

162
00:13:28,950 --> 00:13:36,080
For example, at Azz, one, two, three and four, and they were loaded, I want to search for it too.

163
00:13:36,540 --> 00:13:41,740
So first of all I will check is when it goes to no is too close to yes.

164
00:13:42,540 --> 00:13:47,300
OK, so what I will do, I will return a net is zero one, so I will return one.

165
00:13:47,880 --> 00:13:55,320
So as soon as this statements get executed I will come here and the execution of basically this program

166
00:13:55,320 --> 00:13:56,550
gets finished.

167
00:13:56,910 --> 00:13:58,550
This function, I'll get finished.

168
00:13:59,100 --> 00:14:07,860
OK, and in case, for example, if the key is not present, suppose there are two elements in the area,

169
00:14:07,870 --> 00:14:08,460
one and two.

170
00:14:08,460 --> 00:14:11,220
And the key that we have to search for is three.

171
00:14:11,550 --> 00:14:15,750
So one is not close to three, two is not close to three.

172
00:14:16,020 --> 00:14:18,600
So this loop will get terminated.

173
00:14:18,600 --> 00:14:20,520
I will reach headline number 13.

174
00:14:20,520 --> 00:14:21,540
Return minus one.

175
00:14:22,200 --> 00:14:24,720
Minus one is an invalid index.

176
00:14:26,850 --> 00:14:32,100
OK, you can also return minus two, minus three anything, any invalid index.

177
00:14:34,200 --> 00:14:41,160
And before bringing the answer, I will check if I get an invalid index, that means King found otherwise,

178
00:14:41,280 --> 00:14:49,490
I found the key at index below as so this is called linear search and how many steps it is taking.

179
00:14:49,830 --> 00:14:53,020
So it is just performing a linear scan over the array.

180
00:14:53,250 --> 00:14:54,930
So it is taking and the steps.

181
00:14:57,410 --> 00:15:07,850
So linear search takes and steps, or you can see the time complexity of linear search is bigger off

182
00:15:07,850 --> 00:15:12,650
and OK, so this is all about linear search.

183
00:15:12,890 --> 00:15:14,510
So this is it for this video.

184
00:15:14,690 --> 00:15:15,260
Thank you.

