Search Search Methods Sequential Search Binary Search in C

Databases exist so that from time to time users can find the necessary entry by entering its key. There is one method for searching information in an unordered array, and another for searching in an ordered array. The standard bsearch () function is included in the set of the standard library of C compilers. However, as in the case of sorting, general-purpose procedures are sometimes not at all effective when used in critical situations because of the overhead associated with their generalization. In addition, the bsearch () function cannot be applied to unordered data.

Search methods

To find information in an unordered array, a sequential search is required, starting with the first element and ending with the detection of suitable data or upon reaching the end of the array. This method is applicable for unordered information, but you can also use it on sorted data. However, if the data is already sorted, you can use a binary search that finds the data faster.

Sequential search

Sequential search is very easy to program. The following function searches the array of characters of known length until an element with the specified key is found:

  / * Sequential search * /
 int sequential_search (char * items, int count, char key)
 {
   register int t;

   for (t = 0; t 

Here items is a pointer to an array containing information. The function returns the index of the matching element, if one exists, or -1 otherwise.

It is clear that sequential search on average browses n / 2 items. At best, it checks only one item, and at worst, n . If the information is stored on disk, the search may take a long time. But if the data is not ordered, sequential search is the only possible method.

Binary search

If the data in which the search is performed is sorted, a method that is far superior to the previous one can be used to find the element - binary search ^[1] . It uses the method of half division. First, check the middle element. If it is larger than the desired key, check the middle element of the first half, otherwise - the middle element of the second half. We will repeat this procedure until the required element is found or until the next element remains.

For example, to find the number 4 in the array

1 2 3 4 5 6 7 8 9

in binary search, the middle element, the number 5, is first checked. Since it is greater than 4, the search continues in the first half:

1 2 3 4 5

The middle element is now 3. This is less than 4, so the first half is discarded. The search continues in part

4 5

This time the item was found.

In a binary search, the number of comparisons is at worst equal to

log ₂ n

In the average case, the number is slightly lower, and at best, the number of comparisons is 1.

Below is a binary search function for arrays of characters. This search can be adapted for arbitrary data structures by changing the comparison fragment.

  / * Binary search * /
 int binary_search (char * items, int count, char key)
 {
   int low, high, mid;

   low = 0;  high = count-1;
   while (low <= high) {
     mid = (low + high) / 2;
     if (key  items [mid]) low = mid + 1;
     else return mid;  / * key found * /
   }
   return -1;
 }

^[1] There are other names: dichotomous search , logarithmic search , search by division in half . This method of data retrieval consists in the fact that the entire set of data is divided in half and it is determined in which of the halves the given data is located, after which the half in which the given one is located is in turn divided in half, etc. The process continues until the next received set becomes equal to the only given one, which will be the desired one, or the fact that the required unknown is not present in this set will be established.