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.