Linear Search Solution

[00:00:00]
>> Bianca Gandolfo: All right, so we are going to go over the solution for linearSearch.
>> Bianca Gandolfo: We're gonna hop right in. All right, so the first thing you want to do is we're gonna need a loop. We can do just a simple, let's do forEach, just for fun. So, we are going to look at each list item, and we're going just check if list item equals our item.

[00:00:35]
If that's true, we can return a few things here. We can return the index. We could return true, we could return false. In this case I'm just gonna return the index. So we're gonna say var, we're gonna say let index equals. So typically when we're doing a search.

[00:00:59]
Negative one means that it wasn't found, so as a typical base for not found we'll just do negative one. So that's why I'm initializing the index as negative one, so if list item equal item, we're gonna need to actually have a second,
>> Bianca Gandolfo: Parameter here. So the API forEach when it calls the callback function.

[00:01:24]
The first thing it calls it with is each item. So the first time, it'll be 2. And it also passes the index. So in this case, for 2, the index is 0. So it's gonna loop through. So if the listItem equals item, we are going to update our index to the current index, and there are a few things to consider.

[00:01:52]
So if you have multiple 90s in this list, how do you handle that? Do you want to return the first one? Do you want to return the last one? These are things that you should be asking your interviewer, and it's going to affect this conditional here. Make sure you always do triple equals.

[00:02:10]
So, in this case, what it's gonna do is it's always gonna return the last index if there's a duplicate. So just keep that in mind, and that's okay for our solution, we just need to return the index. So if it doesn't find anything, it's just gonna return negative 1.

[00:02:27]
>> Speaker 2: Okay, how does it know what the value of i is? It just knows that, hey, since we passed in an array as an argument, I know it inherently will have an index.
>> Bianca Gandolfo: So underneath for each, you can imagine in the internals of JavaScript, it's looping and it's calling this function, and when it invokes the function it passes three things actually.

[00:02:53]
It passes the item, it passes the index and it passes the list. So,
>> Bianca Gandolfo: Yeah, that's just how it works, yeah. Often if you don't need the index, you don't need to reference it, but it's there if you want it, yeah, exactly. Okay, let's check our solution, 0, 1, 2, 3, cool and then you search.

[00:03:18]
Any question? What do we think the time complexity of something like this is?
>> Speaker 3: Linear.
>> Bianca Gandolfo: Linear, yeah, yeah, exactly. Cuz in the worst case, 90 is always at the end, right? And you'd have to run through the entire array until you get to 90. Now, best case is the first one and then it would just be, do one thing but we're kind of thinking in worst case and we're thinking about in general.

[00:03:48]
Not for a specific example when we're estimating time complexity.
>> Bianca Gandolfo: All right, any questions? Mm-hm.
>> Speaker 4: I thought we mentioned previously that the for each and the map were a little bit more complicated, was this?
>> Bianca Gandolfo: They are in a way, you can consider, so for each is just a loop under the hood.

[00:04:12]
The thing that makes it a little more complicated is that it kind of depends on what you're doing in the callback. So, since in this callback we're only doing constant timed operations. We're doing a comparison check. We are assigning a variable. Those are all constant. We don't have to worry about it.

[00:04:29]
However, if this was doing maybe another loop. If it was doing some recursion or was doing something that wasn't constant time. Then that's when it gets a little more complicated. Yeah, good question.