Comp 110 Linear Search

Linear Search


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


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)