Mhkonline Tutorials :: C C++ Tutorials -> Structures and Unions

Searching Algorithms \ Techniques

Programming Language	C
Difficulty	Beginner
Date Added	31 Jan 2007

Introduction

The most commonly used searching techniques for arrays are the linear search and binary search algorithms. Here we will have a look at both of them. The aim of a searching algorithm is to find the element to be found is located. If it cannot be located the search is said to be unsuccessful.

1. Linear Search

This is the simplest method of searching. The element to be found is consecutively looked up in the list. The advantage is that it can be applied to an unsorted array. If the length of the array becomes large, this algorithm's performance will decrease. On average, it has to compare (n/2) elements if the array has n elements. If the element is absent, it can be known only after checking all the n elements.

You can use the animation above to understand the simple function of linear search. We will give the function to perform the linear search. The user must be able to write the main function for reading the arrays and calling this function.

/* Linear Search Function
Centrum inc Software Solutions | Jan 2007
input : array, array size, element to look for
returns : posn of key, if not found, returns -1
*/

int linear_search(int a[], int size, int key)
{
    int i, pos = -1; // loop variable and initial posn
    for(i = 0; i < size; i++)
    {
        if(a[i] == key)
        {
             pos = i;
             break;
        }
    }
    return (posn);
}

2. Binary Search

This is a more advanced searching algorithm. It is very fast and efficient. But it requires that the array be sorted before it can perform searching.

The first thing you should know is to keep track of three variables, low, mid and high. Here instead of comparing each element with the key element, we just compare the key element with the element in the middle of the sorted array. If it matches, the search is uccessful else the list is divided into two subparts. If the key element is smaller than the middle element, it should be in the first part else in the second part. The list to search has now halved.

Searching continues in either of the two halves by comparing the key element with the middle value each time until either the element is found or till there is only one element in a half.

The maximum no of comparisons in binary search is log₂ n.

/* Binary Search Function
* Centrum inc Software Solutions | Jan 2007
* input : sorted array, array size, key element
* returns : posn of the key element if found, else returns -1
*/

int binary_search(int a[], int size, int key)
{
/* it is assumed that the given array is sorted, else code for sorting coz this section deals with searching only*/
    int pos = -1, low = 0, high = size -1, mid; // variables for binary search

   while ( low < high)
   {
        mid = (low + high) /2;

        if ( a[mid] == key ) // element found
           { pos = mid; break; }
        else if ( arr[mid] > key )
            upper = mid - 1;
        else
            lower = mid + 1;
    }
    return (pos);
}

Comparison of Linear Search and Binary Search

Suppose we have an array 1,2,3,9,11,13,17,25,57,90. If we want to search 25 in this set, the number of comparisons needed would be

Linear Search : 8
Binary Search : 3

Thus it is clear that Binary Searching is fastre and more efficient. The main advantage is that after each iteration it reduces the number of elements to be searched from n to n/2. On the other hand, linear search checks sequentially for every element, making it inefficient.

The disadvantage of binary search is that it only works on a sorted array or list. If we have to search an unsorted array, we would be forced to use linear search.


Home • ae • Downloads •Solutions •Tutorials • Info • All Tutorials