Linear search

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.

Linear search looks like the following in pseudocode:

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

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