Wikipedia: Linear search

Difference (from prior author revision) (no other diffs)

Changed: 5c5

Linear search looks like the following in pseudocode:

Here is sample implementation in Ruby:

Changed: 7,18c7,18

Input is a list L and a value V. L[x] will denote the xth element in L, which consists of N values, L[1], L[2], ..., L[N].

function linear-search(L,N,V)
set index = 1
repeat while index <= N
if L[index] = V
return success
end-if
set index = index + 1
end-repeat
return failure
end-function


 def linear_search(array,value)
     i = 0
     while (i < array.size-1)
         if (array[i] == value)
             return true
         end
         i += 1
     end
     return false
 end

Changed: 23c23

/Talk

Linear search is a search algorithm suitable for searching a set of data for a particular value.

It operates by checking every element of a list until a match is found. Linear search runs in O(N). If the data is distributed randomly, on average N/2 comparisons will be needed. The best case is that the value is equal to the first element tested, in which case only 1 comparison is needed. The worst case is that the value is not in the list, in which case N comparisons are needed.

Here is sample implementation in Ruby:

def linear_search(array,value)
    i = 0
    while (i < array.size-1)
        if (array[i] == value)
            return true
        end
        i += 1
    end
    return false
end

Linear search is used to search an unordered list. Binary search is used to search an ordered list. If many searches are needed on an unchanging list, it may be faster to sort the list first, and then use Binary Search, which runs in O(log N).

/Talk