Array Searching Algorithms in C

1.Linear Search

Description:
An iterator traverses sequentially the array from left to right. When it encounters an element which is equal to the key the search stops and the index of that element is returned. If the key is not present in the array the size of the array will be returned.
Usage:
It's mostly used when one has no information about the array.
Complexity:
O(n)
Example:

/*
 * Description:
 *  Returns the index of key in array
 * Parameters:
 *  key - the element who is searched for
 *  array - the array who is searched
 *  arraySize - the size of array
 * Returns:
 *  The index of key if key exists in the array.
 *  Otherwise returns arraySize.
 */
int ArraySearch_Linear(int key, int array[], int arraySize)
{
   int i = 0;
   for(i=0;i<arraySize && array[i]!=key; i++);
   return i;
}

2.Sentinel Linear Search

Description:
The algorithm is very similar to the linear search with the exception that the loop invariant is reduced by assigning the value of the key to the last element of the array.
Usage:
It's mostly used when one has no information about the array.
Complexity:
O(n)

/*
 * Description:
 *  Returns the index of key in array
 * Parameters:
 *  key - the element who is searched for
 *  array - the array who is searched
 *  arraySize - the size of array
 * Returns:
 *  The index of key if key exists in the array.
 *  Otherwise returns arraySize.
 */
int ArraySearch_Sentinel(int key, int array[], int arraySize)
{
   int i = 0;
   array[arraySize] = key;
   for(i=0; array[i]!=key; i++);
   return i;
}

3.Binary Search

Description:
The array is divided successively into two parts at each iteration according to the value of the key and the value of the pivot (which is initialized to half of the length of the array).
Usage:
It can only be used when the array is already sorted.
Complexity:
O(log2n)

/*
 * Preconditions:
 *  The array must be sorted
 * Description:
 *  Returns the index of key in array
 * Parameters:
 *  key - the element who is searched for
 *  array - the array who is searched
 *  arraySize - the size of array
 * Returns:
 *  The index of key if key exists in the array.
 *  Otherwise returns arraySize.
 */
int ArraySearch_Binary(int key, int array[], int arraySize)
{
   int left=0;
   int right=arraySize-1;
   int middle = (left+right)/2;
   while(array[middle]!=key && left<=right)
   {
      (key>array[middle])?(left=middle+1):(right=middle-1);
      middle = (left+right)/2;
   }
   return (array[middle]!=key)?(arraySize):(middle);
}

4.Improved Binary Search

Description:
This algorithm brings an improvement over the binary search by removing a condition from the loop invariant (there is no longer needed to check if the pivot is equal to the key the pivot will be calculated differently).
Usage:
It can only be used when the array is already sorted.
Complexity:
O(log2n)

/*
 * Preconditions:
 *  The array must be sorted
 * Description:
 *  Returns the index of key in array
 * Parameters:
 *  key - the element who is searched for
 *  array - the array who is searched
 *  arraySize - the size of array
 * Returns:
 *  The index of key if key exists in the array.
 *  Otherwise returns arraySize.
 */
int ArraySearch_ImprovedBinary(int key, int array[], int arraySize)
{
   int left=0;
   int right=arraySize;
   int middle = (left+right)/2;
   while(left<right)
   {
      (key>array[middle])?(left=middle+1):(right=middle);
      middle = (left + right)/2;
   }
   return ((right>=arraySize)||(right<arraySize && array[right]!=key))
          ?arraySize
          :right;
}

5.Interpolation Search

Description:
This algorithm brings another improvement over the binary search by changing the way the pivot is calculated.
Usage:
It can only be used when the array is already sorted and the differences between elements are somewhat constant.
Complexity:
O(log2n)

/*
 * Preconditions:
 *  The array must be sorted
 * Description:
 *  Returns the index of key in array
 * Parameters:
 *  key - the element who is searched for
 *  array - the array who is searched
 *  arraySize - the size of array
 * Returns:
 *  The index of key if key exists in the array.
 *  Otherwise returns arraySize.
 */
int ArraySearch_Interpolation(int key, int array[], int arraySize)
{
   int left=0;
   int right=arraySize-1;
   int pivot=arraySize;
   if(key<=array[right] && key>=array[left])
   {
      do
      {
         pivot=left+(key-array[left])*(right-left)/(array[right]-array[left]);
        (key>array[pivot])?(left=pivot+1):(right=pivot-1);
      }while(array[pivot]!=key && left<right && array[left]!=array[right]
             && key>=array[left] && key<=array[right]);
   }
   return pivot;
}

Useful links
Array Searching Visualisation Applet