1 00:00:02,150 --> 00:00:03,710 Hey, guys, what's up? 2 00:00:04,100 --> 00:00:10,780 So in this video, we will learn how to search for a given key in an area. 3 00:00:11,380 --> 00:00:12,770 Okay, so what will happen? 4 00:00:13,280 --> 00:00:14,740 We will be given an area. 5 00:00:15,500 --> 00:00:16,430 So we have an area. 6 00:00:16,490 --> 00:00:19,630 And later, the elements are 10, 20. 7 00:00:20,240 --> 00:00:21,830 Three, four. 8 00:00:22,400 --> 00:00:23,930 One zero. 9 00:00:24,590 --> 00:00:24,810 OK. 10 00:00:25,190 --> 00:00:30,770 So we have an array and let's say we have to search for 20. 11 00:00:32,060 --> 00:00:32,320 OK. 12 00:00:32,620 --> 00:00:36,130 So we have to search for a given value in Eddie. 13 00:00:37,720 --> 00:00:41,830 And we have to tell whether the given value is present or not present. 14 00:00:42,430 --> 00:00:46,210 So zero, one, two, three, four and five. 15 00:00:46,690 --> 00:00:48,010 So these are my indexers. 16 00:00:49,430 --> 00:00:49,700 OK. 17 00:00:50,860 --> 00:00:55,080 So, for example, in this case, 20 is present. 18 00:00:55,390 --> 00:00:56,880 So our vote will be one. 19 00:00:57,670 --> 00:00:57,910 OK. 20 00:00:58,000 --> 00:01:02,290 One means index that is 10 days present at index one. 21 00:01:03,370 --> 00:01:09,970 So, for example, if the key that we have to search for is a party today is not present. 22 00:01:10,360 --> 00:01:13,390 So now it should be not present. 23 00:01:14,680 --> 00:01:17,230 Or you can say key not found. 24 00:01:17,890 --> 00:01:20,440 Key not found. 25 00:01:21,470 --> 00:01:24,290 And here we have found key. 26 00:01:25,400 --> 00:01:27,140 At edition. 27 00:01:29,480 --> 00:01:29,840 When. 28 00:01:30,530 --> 00:01:30,820 OK. 29 00:01:31,180 --> 00:01:35,120 So you never give us an error and you never gave us. 30 00:01:35,140 --> 00:01:37,740 For the value that we have to search in the area. 31 00:01:38,380 --> 00:01:43,780 And if the given key is present in the area, you have to print that. 32 00:01:43,900 --> 00:01:44,350 Yes. 33 00:01:44,620 --> 00:01:46,000 The given key is present in that. 34 00:01:46,330 --> 00:01:47,830 And it is present at position. 35 00:01:47,830 --> 00:01:54,670 When and if the given key is not present in the area, then your output should be the given keys, not 36 00:01:54,850 --> 00:01:55,300 present. 37 00:01:55,900 --> 00:01:56,090 OK. 38 00:01:56,500 --> 00:01:58,870 So this is the task that we have to perform. 39 00:01:59,170 --> 00:02:00,700 So how against all this problem. 40 00:02:01,510 --> 00:02:04,060 So the algorithm for solving this problem is very simple. 41 00:02:05,180 --> 00:02:05,830 What we will do. 42 00:02:06,070 --> 00:02:06,920 They will scan that. 43 00:02:07,750 --> 00:02:11,800 We will scan Eddie from left to right. 44 00:02:12,670 --> 00:02:12,940 OK. 45 00:02:13,210 --> 00:02:15,460 So starting from zero to end, minus one. 46 00:02:15,820 --> 00:02:24,130 We will scan the eddy, for example, my arrays, let's say five four two one three zero. 47 00:02:24,640 --> 00:02:29,380 And the value for which we have to search and let's say my key is two. 48 00:02:29,680 --> 00:02:30,610 So what we will do. 49 00:02:31,540 --> 00:02:32,170 I will check. 50 00:02:32,650 --> 00:02:34,010 Is five for close to No. 51 00:02:34,720 --> 00:02:35,770 Is 40 close to. 52 00:02:35,940 --> 00:02:36,370 No. 53 00:02:36,640 --> 00:02:37,450 Is too close to. 54 00:02:37,520 --> 00:02:37,890 Yes. 55 00:02:37,990 --> 00:02:39,370 Too close to stop. 56 00:02:40,750 --> 00:02:47,860 So ultimately, what we are doing, we are scanning the area from left to right, from zero to index 57 00:02:47,950 --> 00:02:48,880 and minus one. 58 00:02:49,240 --> 00:02:52,930 Similarly, if we have to search for, let's say zero. 59 00:02:53,260 --> 00:02:54,820 So is five equals zero? 60 00:02:54,910 --> 00:02:55,360 No. 61 00:02:55,690 --> 00:02:56,680 Four equals zero. 62 00:02:56,770 --> 00:02:57,220 No. 63 00:02:57,460 --> 00:02:58,360 Two equals zero. 64 00:02:58,420 --> 00:03:00,190 No one equals zero. 65 00:03:00,280 --> 00:03:00,700 No. 66 00:03:00,940 --> 00:03:01,930 Three equals zero. 67 00:03:01,990 --> 00:03:02,380 No. 68 00:03:02,740 --> 00:03:04,210 Zero equals zero. 69 00:03:04,240 --> 00:03:04,660 Yes. 70 00:03:06,640 --> 00:03:11,530 Key found, key found at position. 71 00:03:11,650 --> 00:03:16,990 We found the key at position, so zero, one, two, three, four and five. 72 00:03:17,500 --> 00:03:19,890 So key found at position five. 73 00:03:21,800 --> 00:03:26,020 OK, suppose the given key is, let's say. 74 00:03:27,250 --> 00:03:27,720 Six. 75 00:03:28,170 --> 00:03:28,490 OK. 76 00:03:28,780 --> 00:03:32,230 So Jack is five equals six. 77 00:03:32,260 --> 00:03:34,180 No is four equals six. 78 00:03:34,210 --> 00:03:34,530 No. 79 00:03:34,900 --> 00:03:35,950 Is two equals six. 80 00:03:35,980 --> 00:03:36,400 No. 81 00:03:36,700 --> 00:03:37,210 Is one. 82 00:03:37,210 --> 00:03:37,810 Equals six. 83 00:03:37,840 --> 00:03:38,260 No. 84 00:03:38,530 --> 00:03:39,550 Is three equals six. 85 00:03:39,580 --> 00:03:39,940 No. 86 00:03:40,180 --> 00:03:40,810 Is zero. 87 00:03:40,810 --> 00:03:41,380 Equals six. 88 00:03:41,410 --> 00:03:41,620 No. 89 00:03:41,680 --> 00:03:42,610 So I will reach here. 90 00:03:43,620 --> 00:03:43,800 OK. 91 00:03:43,870 --> 00:03:44,890 So I will reach everybody. 92 00:03:44,920 --> 00:03:45,360 Shannon. 93 00:03:45,640 --> 00:03:48,810 That means gay sex is not present. 94 00:03:51,270 --> 00:03:54,230 Physics is not present in the Eddie. 95 00:03:56,740 --> 00:03:58,450 So our algorithm is very simple. 96 00:03:58,900 --> 00:03:59,650 What we will do. 97 00:04:00,040 --> 00:04:01,390 We will scan the area. 98 00:04:02,020 --> 00:04:03,220 We will Scandi Eddie. 99 00:04:03,920 --> 00:04:04,190 Okay. 100 00:04:04,660 --> 00:04:05,860 So very simple. 101 00:04:06,780 --> 00:04:08,770 So our Corbel look something like this. 102 00:04:10,290 --> 00:04:11,130 I will start. 103 00:04:12,390 --> 00:04:20,460 I will start scanning from zero till the last position and what I will check. 104 00:04:20,610 --> 00:04:28,470 I will check if the current value is equal to Gey that we have to search, then yes. 105 00:04:28,560 --> 00:04:29,200 See out. 106 00:04:29,490 --> 00:04:29,910 Found. 107 00:04:30,940 --> 00:04:31,860 Found the key. 108 00:04:33,520 --> 00:04:41,180 Found key and similarly, if the value of AI becomes an end, we also break. 109 00:04:41,570 --> 00:04:41,870 OK. 110 00:04:42,490 --> 00:04:44,800 After we found the key, we will break. 111 00:04:45,220 --> 00:04:50,500 So if the value of AI close N, that means this Lopez terminated naturally. 112 00:04:51,790 --> 00:04:52,930 So this Lubitch terminated. 113 00:04:53,140 --> 00:04:55,200 Naturally, that means the value of AI becomes. 114 00:04:55,320 --> 00:04:58,750 And so we can say gey not found. 115 00:04:59,770 --> 00:04:59,920 OK. 116 00:05:00,220 --> 00:05:02,650 So we are just doing the linear scan. 117 00:05:03,580 --> 00:05:04,960 We are just doing the linear scan. 118 00:05:04,960 --> 00:05:06,910 And each time I am comparing the value. 119 00:05:07,270 --> 00:05:08,680 If I got a match. 120 00:05:08,830 --> 00:05:12,890 I am printing as the key found and I'm breaking the loop. 121 00:05:13,620 --> 00:05:13,910 OK. 122 00:05:14,470 --> 00:05:16,230 And if the value of AI becomes n. 123 00:05:16,780 --> 00:05:19,420 That means this loop is terminated naturally. 124 00:05:19,630 --> 00:05:22,480 This big statement has not been executed. 125 00:05:22,780 --> 00:05:25,860 And that means the key is not present in the area. 126 00:05:27,250 --> 00:05:28,270 So let the slide called. 127 00:05:29,890 --> 00:05:33,350 So I have named this file as linear, so it's not TPP. 128 00:05:34,000 --> 00:05:41,980 So via name this file as linear search because I am searching, I am searching linearly. 129 00:05:42,990 --> 00:05:43,230 OK. 130 00:05:43,330 --> 00:05:46,670 So I am doing searching linearly. 131 00:05:46,810 --> 00:05:49,750 So that's why they call it linear search. 132 00:05:50,930 --> 00:05:57,520 OK, so this is called Línea Search Wiliness Search because I am searching linearly. 133 00:05:58,930 --> 00:06:01,610 So the name of this vial is Lenience Usdaw TBP. 134 00:06:02,180 --> 00:06:06,790 So first let us take it and let us take input. 135 00:06:09,260 --> 00:06:10,610 Now let us make any. 136 00:06:13,940 --> 00:06:16,880 Now, let us take the values off areas input. 137 00:06:23,830 --> 00:06:29,270 So what I am writing, I am writing a function and it will give me position. 138 00:06:30,940 --> 00:06:32,940 So I have a function. 139 00:06:33,760 --> 00:06:36,530 The name of the function is linear, linear search. 140 00:06:37,720 --> 00:06:41,170 OK, so linear search function will take two linear sites. 141 00:06:41,170 --> 00:06:42,190 Function will take Eddie. 142 00:06:42,760 --> 00:06:44,500 And the size of that is input. 143 00:06:44,890 --> 00:06:48,940 And it will return me the position at which the number is present. 144 00:06:49,000 --> 00:06:49,960 The key is present. 145 00:06:50,420 --> 00:06:51,280 Well, moulting here. 146 00:06:51,940 --> 00:06:55,390 We also need to take the key for which we have to search Soucy out. 147 00:06:56,110 --> 00:06:57,190 And the key. 148 00:07:02,250 --> 00:07:06,690 So let us make a variable in the key and see in key. 149 00:07:07,870 --> 00:07:08,100 OK. 150 00:07:08,610 --> 00:07:10,440 So we also need to pass key here. 151 00:07:10,560 --> 00:07:12,990 So Leena's, it will take three arguments. 152 00:07:13,230 --> 00:07:14,580 Eddie, the size of dairy. 153 00:07:15,060 --> 00:07:20,130 And the key for which it will search and word linear function will return. 154 00:07:20,190 --> 00:07:25,290 They Nessa's function will return midi position at which the given key is present. 155 00:07:26,630 --> 00:07:29,980 So let's make the function so that we don't typist. 156 00:07:30,120 --> 00:07:34,910 And because we will retain the position, name of the function is linear. 157 00:07:37,830 --> 00:07:41,440 Search and it is taking three arguments as input. 158 00:07:41,820 --> 00:07:49,590 So and Eddie, the size of the Eddie and the third argument or the third about amateur's the key for 159 00:07:49,590 --> 00:07:53,130 which it will do search it will perform search operation. 160 00:07:53,970 --> 00:07:58,320 So what I have to do, I have to do just a linear scan of the area so far. 161 00:07:59,460 --> 00:08:01,500 And I equals zero. 162 00:08:01,690 --> 00:08:06,910 I less than an A plus plus what I have to do. 163 00:08:07,000 --> 00:08:08,430 Compare the current value. 164 00:08:09,390 --> 00:08:13,500 Compare the current value, which is zero phi with the given key. 165 00:08:13,890 --> 00:08:18,420 And if you've got a match, that means the given key is present in the area. 166 00:08:18,720 --> 00:08:22,470 So you will return I guess. 167 00:08:22,480 --> 00:08:23,120 Or you will return. 168 00:08:23,130 --> 00:08:24,600 I, I means. 169 00:08:25,690 --> 00:08:30,850 So what I have to done, I have to return the position at which the given case present, so the given 170 00:08:30,860 --> 00:08:34,060 case, present and position I so I am returning I. 171 00:08:35,370 --> 00:08:38,000 And if this loop got terminated. 172 00:08:39,000 --> 00:08:44,680 So if I reach line number 10, that means the given key is not present in the eddy. 173 00:08:46,350 --> 00:08:47,760 Then I can return. 174 00:08:48,840 --> 00:08:50,880 I can return minus one. 175 00:08:53,250 --> 00:08:59,840 OK, so if the given key is not present in the area, what will happen, this written ICE statement 176 00:08:59,960 --> 00:09:02,120 will never be executed. 177 00:09:03,340 --> 00:09:08,340 So if this statement is never executed, this loop will get terminated naturally. 178 00:09:09,860 --> 00:09:15,570 And if this loop gets damaged naturally, that means the given key is not present in the area. 179 00:09:16,160 --> 00:09:22,430 And I'm returning minus one Y minus one Magos minus one is nota valid index. 180 00:09:22,910 --> 00:09:25,820 You can also return minus 10, minus two and B minus three. 181 00:09:25,820 --> 00:09:26,330 Minus four. 182 00:09:26,330 --> 00:09:28,250 Minus five, minus hundred. 183 00:09:28,390 --> 00:09:28,680 OK. 184 00:09:29,210 --> 00:09:32,810 So you just have to return an invalid index. 185 00:09:32,930 --> 00:09:35,090 So minus one is an invalid index. 186 00:09:35,330 --> 00:09:36,760 So I'm returning minus one. 187 00:09:38,300 --> 00:09:39,980 So this is the politician. 188 00:09:41,090 --> 00:09:45,950 So first of all, I will check if the position. 189 00:09:47,450 --> 00:09:55,220 So if the position equals equals minus one, that means the given key is not present in the EDDI. 190 00:09:55,730 --> 00:09:56,890 So you can see out. 191 00:09:59,660 --> 00:10:04,900 Keen found, key not found. 192 00:10:06,170 --> 00:10:12,280 OK, as we can safely say that the given key is present. 193 00:10:12,870 --> 00:10:23,070 OK, so see out key fund and index perdition. 194 00:10:27,250 --> 00:10:28,780 OK, so this is our entire call. 195 00:10:28,930 --> 00:10:29,800 Let's see it again. 196 00:10:30,400 --> 00:10:34,900 So lenience, its function is taking three arguments, three barometer's as input. 197 00:10:35,380 --> 00:10:36,940 I am doing a linear scan. 198 00:10:37,270 --> 00:10:40,540 I am conveying the value of key with the current value. 199 00:10:40,900 --> 00:10:42,910 If I got a match, I will return I. 200 00:10:43,750 --> 00:10:44,110 OK. 201 00:10:45,010 --> 00:10:47,010 So this function will return any data. 202 00:10:47,070 --> 00:10:49,270 That is position at which that key is found. 203 00:10:49,990 --> 00:10:53,590 And if this loop got damaged, naturally I am returning minus one. 204 00:10:53,590 --> 00:10:56,350 Minus one means are invalid index. 205 00:10:56,650 --> 00:10:58,630 That means key not found. 206 00:10:59,110 --> 00:11:00,830 So it is my position. 207 00:11:00,940 --> 00:11:03,370 I am checking if potion equals minus one key. 208 00:11:03,520 --> 00:11:05,380 Not found otherwise. 209 00:11:05,840 --> 00:11:08,360 Key found at index position. 210 00:11:10,920 --> 00:11:11,820 So let's compile. 211 00:11:15,680 --> 00:11:18,000 OK, so it will be darte. 212 00:11:22,910 --> 00:11:24,290 OK, it will be see in. 213 00:11:30,130 --> 00:11:31,300 So let's say that our. 214 00:11:32,570 --> 00:11:37,610 Five elements and the elements are one, two, three, four and five. 215 00:11:38,620 --> 00:11:41,450 So and Turkey, for example, I went to search for three. 216 00:11:42,650 --> 00:11:44,750 So the key found at next to. 217 00:11:45,080 --> 00:11:48,830 OK, so this is a neck zero in the X1 and X2. 218 00:11:49,130 --> 00:11:50,960 So three found at index to. 219 00:11:53,830 --> 00:12:02,830 One more time led to a number of elements are formed and the elements are five, seven, eight and zero. 220 00:12:04,440 --> 00:12:06,780 So Angeliki, I want to search for zero. 221 00:12:08,050 --> 00:12:10,000 So we found at index three. 222 00:12:10,180 --> 00:12:11,460 So this is at index three. 223 00:12:12,160 --> 00:12:14,500 OK, indexing at a start from zero. 224 00:12:16,230 --> 00:12:17,100 Now, last time. 225 00:12:18,300 --> 00:12:25,380 Suppose a number of elements are five and the elements are one, two, three, four and five. 226 00:12:26,190 --> 00:12:27,960 And I want to search for six. 227 00:12:29,150 --> 00:12:30,450 So key not found. 228 00:12:30,740 --> 00:12:31,050 Okay. 229 00:12:31,470 --> 00:12:32,670 Key not found. 230 00:12:36,790 --> 00:12:38,710 Now, one last thing that I want to clear. 231 00:12:41,520 --> 00:12:49,350 OK, so, for example, if my airways one, two and three and my key is one, OK? 232 00:12:49,730 --> 00:12:51,260 So what will happen equals zero. 233 00:12:51,350 --> 00:12:54,890 Less than an A plus plus of zero initially. 234 00:12:55,020 --> 00:12:58,110 Well if I zero eight zero eight koskie. 235 00:12:58,370 --> 00:12:59,510 So one equals one. 236 00:13:00,200 --> 00:13:02,200 One equals one return I. 237 00:13:02,540 --> 00:13:04,590 So I is zero zero one two. 238 00:13:04,960 --> 00:13:05,690 So return eight. 239 00:13:05,690 --> 00:13:06,710 That is return zero. 240 00:13:07,430 --> 00:13:07,640 OK. 241 00:13:07,730 --> 00:13:12,800 So as soon as this return statement is executed, this program is finished. 242 00:13:13,730 --> 00:13:13,980 OK. 243 00:13:14,440 --> 00:13:16,420 This this function is finished. 244 00:13:17,320 --> 00:13:19,630 If this written statement is executed, I regret it. 245 00:13:19,660 --> 00:13:22,990 Later it the venue and the program will not be executed. 246 00:13:26,170 --> 00:13:27,010 So one more time. 247 00:13:29,010 --> 00:13:33,210 For example, adays one, two, three and four. 248 00:13:33,630 --> 00:13:36,060 And the value that I want to search for is two. 249 00:13:36,600 --> 00:13:41,190 So first of all, I will check is when it goes to no is too close to. 250 00:13:41,310 --> 00:13:41,790 Yes. 251 00:13:42,650 --> 00:13:42,930 OK. 252 00:13:43,200 --> 00:13:46,250 So what I will do, I will return a net is zero one. 253 00:13:46,320 --> 00:13:47,280 So I will return one. 254 00:13:47,940 --> 00:13:52,320 So as soon as this statement get executed, I will come here. 255 00:13:52,710 --> 00:13:56,550 And the execution of basically this program gets finished. 256 00:13:57,000 --> 00:13:58,530 This function get finished. 257 00:13:59,280 --> 00:13:59,520 OK. 258 00:14:01,240 --> 00:14:07,810 And in case, for example, of the given case not present, suppose there are two elements in the area. 259 00:14:07,870 --> 00:14:08,470 One and two. 260 00:14:08,470 --> 00:14:11,140 And the key that we have to search for history. 261 00:14:11,620 --> 00:14:13,870 So one is not to close to three. 262 00:14:14,290 --> 00:14:15,820 Two is not to close to three. 263 00:14:16,090 --> 00:14:18,550 So this loop will get terminated. 264 00:14:18,610 --> 00:14:20,470 I will reach at line number 13. 265 00:14:20,560 --> 00:14:21,550 Return minus one. 266 00:14:22,270 --> 00:14:24,720 Minus one is an invalid index. 267 00:14:26,980 --> 00:14:27,240 OK. 268 00:14:27,610 --> 00:14:29,830 You can also read minus two, minus three. 269 00:14:29,850 --> 00:14:32,140 Anything, any invented index. 270 00:14:34,290 --> 00:14:38,680 And before printing answer, I will check if I get an invalid index. 271 00:14:38,860 --> 00:14:41,050 That means Keehner found otherwise. 272 00:14:41,400 --> 00:14:43,760 I found the key at index B. 273 00:14:43,760 --> 00:14:44,020 U. 274 00:14:44,120 --> 00:14:44,390 S. 275 00:14:45,180 --> 00:14:47,310 So this is called linear search. 276 00:14:47,730 --> 00:14:49,500 And how many steps it is taking. 277 00:14:49,890 --> 00:14:53,020 So it is just performing a linear scan over the array. 278 00:14:53,340 --> 00:14:54,960 So it is taking and the steps. 279 00:14:57,470 --> 00:15:07,810 So, Lina, search takes an steps, or you can say that time complexity of linear search is bigger off 280 00:15:07,900 --> 00:15:08,140 and. 281 00:15:09,680 --> 00:15:09,980 OK. 282 00:15:10,490 --> 00:15:12,670 So this is all about linear search. 283 00:15:12,980 --> 00:15:14,540 So this isn't for this video. 284 00:15:14,750 --> 00:15:15,260 Thank you.