Linear search looks like the following in pseudocode: |
Here is sample implementation in Ruby: |
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 |
|
/Talk |
/Talk |
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).