What is a Linear Search?

A linear search is a very basic searching method. In it, the array (or other data structure, such as linked list) is iterated through until the desired item is found.

1D Array Example

searchFunction(int list[], int n, int value) {
	// searches through the inputted array and returns the index where value is found
	// if no value is found in the list, return -1
	for (int i = 0; i < n; ++i) {
		if (list[i] == value) {
			return i;
		}
	}
	return -1;
}

Linear Search is Pretty Slow

The maximum number of comparisons to find a match with $n$ values is $n$ comparisons, and the average is $\frac{n}{2}$. So, this is very inefficient. Binary search is a much more efficient method.