Linear search

Best Case: 1

Average Case: n

Worst Case: n

Linear Search is a simple searching algorithm which loops through each element. It's not very effcient or fast because it has to search through each element individually which is not good for very large data sets. requires very little code to implement simply needs a for loop and an if statement.

The following example implements a small function that searches for a value and returns it if found.

C++/C example

   
int LinearSearch(int A[], int size, int x) {
    for (int i = 0; i < size; i++)
        {
            if (A[i] == x)
            {
            return i;
            }
        }
    return -1;
}

int main() {

int A[] = {0, 2, 5, 6, 7, 8, 9, 10, 11, 12};
int x = 9;
int size = sizeof(A)/sizeof(A[0]);

int location = LinearSearch(A, size, x);

if (location == -1) {
    std::cout << "Element not found" << std::endl;
} else {
    std::cout << "Element found at: " << location << std::endl;
}

return 0;
}
                

Summary

Generally not ideal for large arrays because of how slow it is, however due to it's simplicity it uses very little compute power so it maybe ideal for older hardware. It could also be multi threaded to boost search speeds at the cost of more processing power.