Question

Assume that you are given an unsorted array that contains 100 items, and you have been asked to write/propose an efficient searching algorithm. Which algorithm would you choose and why? What are the possible trad-offs of the selected algorithm if the array size is increased (e.g., 9000 items)?

Answer 1

Sequential Search

If you want to find the position in an unsorted array of n integers that stores a particular value, we cannot really do better than simply looking through the array from the beginning and move toward the end until you find what you are looking for. This algorithm is called sequential search.

Here is a simple implementation for sequential search.

JAVA CODE :

// Return the position of an element in array A with value K.
// If K is not in A, return A.length.
static int sequential(int[] A, int K) {
  for (int i=0; i<A.length; i++) // For each element
    if (A[i] == K)               // if we found it
       return i;                 //   return this position
  return A.length;               // Otherwise, return the array length
}

C++ CODE :

// Find the position in A that holds value K, if any does
int sequential(int A[], int size, int K) {
  for (int i=1; i<size; i++)     // For each element
    if (A[i] == K)               // if we found it
       return i;                 //   return this position
  return size;                   // Otherwise, return the array length
}

In the case of sequential search, it is easy to see that if the value is in position i of the array, then sequential search will look at i values to find it. If the value is not in the array at all, then we must look at n values if the array holds n values. This would be called the worst case for sequential search.

Since the amount of work is proportional to n, we say that the worst case for sequential search has linear cost. For this reason, the sequential search algorithm is sometimes called linear search.

It will work great with both type of data i.e. 100 items as well as 9000 items.