## Linear Search

### Algorithm

1.) Start at the beginning of an array

2.) Iterate through each element

- Test for a match
- If match is found, return it

3.) Else no match is found

### Example

Take the following array "arr":

Let's say we want to find the location of number "6".

We start at step 1.), at the beginning of the array. Is arr[0] == 6? No, it isn't so we continue on. We continue this until we reach the value 6.

public int linearSearch(int key){
//returns -1 if it cannot find the key in the array
//return the index if it can find the key in the array
for(int i = 0; i < arr.length; i++){
if(arr[i] == key){
return i;
}
}
return -1;
}

### Run Time

Worst case: O(N)

Best case: O(1)