1 00:00:00,000 --> 00:00:02,892 >> [MUSIC PLAYING] 2 00:00:02,892 --> 00:00:05,347 3 00:00:05,347 --> 00:00:07,180 DOUG LLOYD: Linear search is an algorithm we 4 00:00:07,180 --> 00:00:09,840 can use to find an element in an array. 5 00:00:09,840 --> 00:00:11,990 An algorithm recall is a step-by-step set 6 00:00:11,990 --> 00:00:15,030 of instructions for completing a task. 7 00:00:15,030 --> 00:00:17,480 >> The linear search algorithm works as follows. 8 00:00:17,480 --> 00:00:22,200 Iterate across the array from left to right, looking for a specified element. 9 00:00:22,200 --> 00:00:26,380 >> In pseudocode, which is a more distilled version of this sentence, 10 00:00:26,380 --> 00:00:29,840 if the first element is what you're looking for, you can stop. 11 00:00:29,840 --> 00:00:33,930 Otherwise, move to the next element and keep going over and over until you find 12 00:00:33,930 --> 00:00:36,389 the element, or you don't. 13 00:00:36,389 --> 00:00:38,680 So we can use the linear search algorithm, for example, 14 00:00:38,680 --> 00:00:42,330 to find the target value nine in this array. 15 00:00:42,330 --> 00:00:43,870 Well we start at the beginning. 16 00:00:43,870 --> 00:00:45,970 If it's what we're looking for, we can stop. 17 00:00:45,970 --> 00:00:47,890 It's not, we're not looking for 11. 18 00:00:47,890 --> 00:00:50,220 So otherwise, move to the next element. 19 00:00:50,220 --> 00:00:51,510 >> So we look at 23. 20 00:00:51,510 --> 00:00:52,730 Is 23 what we're looking for? 21 00:00:52,730 --> 00:00:55,614 Well no, so we move on to the next element, and the next element, 22 00:00:55,614 --> 00:00:57,780 and we keep going through this process over and over 23 00:00:57,780 --> 00:01:01,030 and over, until we land on a situation like this. 24 00:01:01,030 --> 00:01:03,910 >> Nine is what we're looking for, and this element of the array 25 00:01:03,910 --> 00:01:05,787 is, it's value is nine. 26 00:01:05,787 --> 00:01:08,120 And so we found what we're looking for, and we can stop. 27 00:01:08,120 --> 00:01:11,910 The linear search has completed, successfully. 28 00:01:11,910 --> 00:01:15,370 >> But what about if we're looking for an element that's not in our array. 29 00:01:15,370 --> 00:01:17,040 Does linear search still work? 30 00:01:17,040 --> 00:01:17,540 Well sure. 31 00:01:17,540 --> 00:01:19,947 So we repeat this process starting at the first element. 32 00:01:19,947 --> 00:01:21,780 If it's what we're looking for, we can stop. 33 00:01:21,780 --> 00:01:22,800 It's not. 34 00:01:22,800 --> 00:01:25,020 Otherwise, we move to the next element. 35 00:01:25,020 --> 00:01:29,050 >> But we can keep repeating this process, examining each element in turn, 36 00:01:29,050 --> 00:01:31,720 hoping that we find the number 50. 37 00:01:31,720 --> 00:01:33,750 But we won't know if we've found the number 50 38 00:01:33,750 --> 00:01:38,290 or if we didn't, until we've stepped over every single element of the array. 39 00:01:38,290 --> 00:01:40,440 >> Only once we've done that and come up short, 40 00:01:40,440 --> 00:01:43,040 can we conclude that 50 is not in the array. 41 00:01:43,040 --> 00:01:46,410 And so the linear search algorithm, well it failed, per se. 42 00:01:46,410 --> 00:01:49,181 But not in the sense that it was unsuccessful in doing what 43 00:01:49,181 --> 00:01:49,930 we asked it to do. 44 00:01:49,930 --> 00:01:52,390 >> It was unsuccessful in as much as it didn't find 50, 45 00:01:52,390 --> 00:01:54,070 but 50 wasn't in the array. 46 00:01:54,070 --> 00:01:57,310 But we have exhaustively searched through every single element 47 00:01:57,310 --> 00:02:00,550 and so, while we didn't find anything, linear search still 48 00:02:00,550 --> 00:02:05,230 succeeds even if the element is not in the array. 49 00:02:05,230 --> 00:02:07,507 >> So what's the worst case scenario with linear search? 50 00:02:07,507 --> 00:02:09,590 Well we have to look through every single element, 51 00:02:09,590 --> 00:02:14,590 either because the target element is the last element of the array, 52 00:02:14,590 --> 00:02:18,510 or the element we're looking for doesn't actually exist in the array at all. 53 00:02:18,510 --> 00:02:19,760 What's the best case scenario? 54 00:02:19,760 --> 00:02:22,430 Well we might find the element immediately. 55 00:02:22,430 --> 00:02:24,360 And how many elements do we then have to look 56 00:02:24,360 --> 00:02:26,859 at in the best case, if we're looking for it 57 00:02:26,859 --> 00:02:28,400 and we find it at the very beginning? 58 00:02:28,400 --> 00:02:29,850 We can stop immediately. 59 00:02:29,850 --> 00:02:32,984 >> What does this say about the complexity of linear search? 60 00:02:32,984 --> 00:02:35,650 Well in the worst case, we have to look at every single element. 61 00:02:35,650 --> 00:02:38,930 And so it runs in O of n, in the worst case. 62 00:02:38,930 --> 00:02:41,540 >> In the best case, we're gonna find the element immediately. 63 00:02:41,540 --> 00:02:44,750 And so runs in omega of 1. 64 00:02:44,750 --> 00:02:45,780 >> I'm Doug Lloyd. 65 00:02:45,780 --> 00:02:48,020 This is CS50. 66 00:02:48,020 --> 00:02:49,876