Searching

Searching refers to finding the location of an element with a specific value within a collection of elements. The simplest search algorithm is the sequential search, which evaluates every element in the array (in order) and compares its value with the one being looked for. The function below demonstrates a sequential search. The function accepts a pointer to an array of integers, the amount of integer in the array, and a number to be looked for in the array. A boolean value is returned specifying whether that number exists in the array.

bool InArray(int *array, int size, int num)
{
   for(int j = 0; j < size; j++)
      if(array[j] == num)
         return true;
   return false;
}

The algorithm is very simple to implement, but also very inefficient. In the average and worst case, it takes O(N) time to find if the item exists. In very large arrays, this is a very slow operation.

A more efficient search can be performed if the array is already sorted. Note, sorting an array first, and then using one of the more efficient search algorithms may be inefficient in the long run. It is recommended that such algorithms be used only if the array is sorted to begin with. The binary search algorithm is one of the simplest searching algorithms on a sorted array. For demonstration purposes, we will assume the array is sorted in ascending order. However, the algorithm can easily be modified to work with descending list by changing the relational operators. The binary search algorithm compares the number being looked for to the value of the middle element in the array. Depending on whether it is less or greater, the same process is then done on the left or right part of the array respectively. One possible implementation of a binary search is shown below.

bool InArray(int *array, int left, int right, int num) //left and right are the left and right index values of the array. These are both necessary as parameters since the function is recursive.
{
   if(num == ((left+right)/2)) //if a match is found, return true
      return true;
   if(left == right) //all possibilities have been searched. num is not in the array
      return false;
   if(num < ((left+right)/2))
      return InArray(array,left,((left+right)/2) - 1,num); //perform the same operation. New right position is the element before the middle
      if(num > ((left+right)/2))
   return InArray(array,((left+right)/2) + 1,right,num); //perform the same operation. New left position is the element directly after the middle.
}

Hasing is a somewhat different approach to searching, as it attempts to make searching O(1) efficiency. A hash function is applied, which uses some type of algorithm or formula to determine what index of an array (also called the hash table) the object should be in. The algorithm or formula depends on the type of data in each situation.

Most times, at least several collisions occur in the hash table. A collision is when an index is returned by the hash function that already has a value. This could mean it is either a duplicate, or the hash function is not unique, which is often times the case. There are two approaches to resolving a collision.

The first is known as open hashing. In this method, collision values are stored "outside" of the array. An example of open hashing is having each array index point to another array, or linked list. Thus, all values that hash to that location are stored in the list. The items in the list can be sorted by their value, access frequency, or the order in which they were put into the table.

Closed hashing is another collision resolution technique. In this approach, the collision values are stored at a different location in the hash table. The hash function takes care of this, as the resolution is dependent on data and programming task. Whatever algorithm the hash function uses to resolve a collision must then be used when searching to find the item required.