Linear Search

excerpt: This covers the building blocks such as Linear Scan, Value Comparison and Early Termination. tags: linear-scan value-comparison early-termination traversing-sequence

A linear search or exhaustive search loops through the items in the array, looking for the target item. The diagram shows a linear search for the value 77.

Linear search can work on linked lists, where it is not easy to jump from one part of the list to another, as you can in an array. Linear search also works on unsorted lists.

Linear Search in Unsorted List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def linearsearch(array, target)
  
  for i in (0..array.size - 1)
    if array[i] == target
      return i
    end
  end
  
  return -1
end

array = [1,2,3,9,4,7]
target = 19
p linearsearch(array, target)

Linear Search in Sorted List

But if the items are sorted, the search can stop if it finds an item with a value greater than the target value. The early stopping saves a little time if the target value is not in the list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def linearsearch(array, target)
  for i in (0..array.size - 1)
    # Check if we found the target
    if array[i] == target
      return i
    end
    
    # Check if we have passed where the target would be
    if array[i] > target
      return -1
    end
    
    # All numbers in the array are smaller than the target
    # The target is not in the array
    return -1
  end
end

The search may check the entire array to conclude that an item is not there, so the worst case runtime is O(N). Even in the average case, the run time is O(N). The number of steps required to search for every item in the array is 1 + 2 + 3 + … + N = N * (N + 1) / 2. The average search time for all the N times is N * (N + 1) / 2 divided by N which is N + 1 / 2, this gives the average runtime of O(N).

Search in String

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def index(word, letter)
  for i in (0..word.size-1)
    if letter == word[i]
      return i
    end
  end
  
  return -1
end

p index('hello', 'o')

Traversing a sequence and returning when we find something we are looking for is called a search.

Building Blocks

• Linear Scan
• Value Comparison
• Early Termination
• Traversing Sequence