Comp 110 Linear Search

Linear Search

Algorithm

1.) Start at the beginning of an array

2.) Iterate through each element

  1. Test for a match
  2. If match is found, return it

3.) Else no match is found


Example

Take the following array  "arr":

341256419632512

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)