• Main Menu
  • Searching


    Searching is the process of finding the location of a given element in a set of elements. The search is said to be successful if the given element is found i.e., the element does exist in the collection (such as an array); otherwise it is unsuccessful.

    Two simple approaches to searching are:

    • Linear search: This method traverses a list sequentially to locate the search key.
    • Binary search: This method works on sorted lists by progressively making better guesses to find the location of a search key.

    Linear Search

    This method traverses a list sequentially to locate the search key.

    The algorithm that one chooses generally depends on the organization of the array elements. If the elements are in random order, then one should choose the linear search technique.

    Algorithm

    linearsearch (a,n,item,loc)

    Here "a" is an array of the size n. This algorithm finds the location of the element "item" in the array "a". If search item is found, it sets loc to the index of the element; otherwise, it sets loc to -1

    Begin for i=0 to (n-1) by 1 do if (a[i] = item) then set loc=I exit endif endfor set loc -1 end

    C/C++ Implementation of the Algorithm

    .cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }

    int linearsearch (int a[], int n, int key)
    {
     int i;
     for(i=0;i<n;i++)

     {
     if(a[i]==key)
     return i;
     }
     return -1;
    }

    Analysis of Linear Search

    In the best possible case, the item may be found at the first position. In that case, the search operation terminates in success with just one comparison.

    The worst case occurs when the item is present at the last position or it is missing from the array. In the former case, the search terminates in success with n comparisons. In the latter case, the search terminates in failure with n comparisons. Thus, we find that in the worst case, linear search carries out n operations.

    Complete Program

    /**
     * Program that illustrates the working of Linear Search
     * http://www.tech-faq.com
     */
     
    #include <stdio.h>
     
    /**
     * Parameters:
     * a: array to search in
     * n: number of elements in the array
     * key: search key
     *
     * Return Value: index of the first occurence
     * of key in a[], or -1 if not found
     */
    int linearsearch (int a[], int n, int key)
    {
     int i;
     for(i=0;i<n;i++)
     {
     if(a[i]==key)
     return i;
     }
     return -1;
    }
     
     
    int main()
    {
     int array[50], num, index, element, key;
     
     /*Fill the array*/
     puts("How many elements do you want to create the array with? (Max 50)");
     scanf("%d", &num);
     
     printf("Enter the elements: ");
     fflush(stdout);
     
     for (index=0; index<num; index++) 
     scanf("%d", &array[index]);
     
     printf("Enter the search key: ");
     fflush(stdout);
     scanf("%d", &key);
     
     if ( (index=linearsearch(array, num, key)) != -1)
     printf("The element was found at index: %dn", index);
     else
     printf("Could not find %dn", key);
     
     return 0;
    }

    Binary Search

    This method works on sorted lists by progressively making better guesses to find the location of a search key.

    Illustration

    Consider the following array:

    3 10 15 20 35 40 60

    Suppose we want to search the element "15"

    1. We take beg = 0, end = 6 and compute the location of the middle element as
      mid = (beg+end)/2 = (0+6)/2 = 3
    2. We then compare the search key with mid i.e. a[mid]=a[3] is not equal to 15. Since beg<end, we start the next iteration.
    3. As a[mid]=20>15, therefore, we take end = mid-1 = 3-1 = 2 whereas beg remains the same.. Thus
      mid = (beg+end)/2 = (0+2)/2 =1
    4. Since a[mid] i.e. a[1]=10<15, therefore, we take beg=mid+1=1+1=2, while end remains the same.
    5. Now beg=end. Compute the mid element:
      mid = (beg+end)/2 = (2+2)/2 = 2
      Since a[mid] i.e. a[2]=15, the search terminates on success.

    Algorithm

    Binarysearch(a,n,item,loc)

    Begin
    set beg=0
    set end=n-1
    set mid=(beg+end)/2
    while((beg<=end) and(a[mid]!=item) do
    if(item<a[mid]) then
    set end=mid-1
    else
    set beg=mid+1
    endif
    set mid=(beg+end)/2
    endwhile
    if(beg>end) then
    set loc=-1
    else
    set loc=mid
    endif
    end

    C/C++ Implementation

    .cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }

    int binarysearch(int a[], int n, int key)
    {
        int beg,end,mid;
        beg=0; end=n-1;
        mid=(beg+end)/2;
        while((beg<=end)&&(a[mid]!=key))
        {
            if(key<a[mid])
                end=mid-1;
            else
                beg=mid+1;
            mid=(beg+end)/2;
        }
        if(beg>end)
            return -1;
        else
            return mid;
    }

    Analysis of Binary Search

    In each iteration, the search is reduced to one-half of the array. For n elements in the array, there will be a maximum of log2 n iterations.

    Thus, the complexity of binary search is O(log2 n).

    Complete Program Listing

    /**
     * Program that illustrates the working of Binary Search
     * http://www.tech-faq.com
     */
     
    #include <stdio.h>
     
    int binarysearch(int a[], int n, int key)
    {
        int beg,end,mid;
        beg=0; end=n-1;
        mid=(beg+end)/2;
        while((beg<=end)&&(a[mid]!=key))
        {
            if(key<a[mid])
                end=mid-1;
            else
                beg=mid+1;
            mid=(beg+end)/2;
        }
        if(beg>end)
            return -1;
        else
            return mid;
    }
     
    int main()
    {
        int arr[50], n, key, index;
     
        printf("How many elements do you want to create the array with?(max 50): ");
        fflush(stdout);
     
        scanf("%d", &n);
     
        puts("Enter the array elements in ascending order");
        for (index = 0; index < n; index++)
            scanf("%d", &arr[index]);
     
        printf("Enter the search key: ");
        fflush(stdout);
     
        scanf("%d", &key);
     
        index = binarysearch(arr, n, key);
     
        if (index == -1)
            puts("Sorry, the given key was not found");
        else
            printf("The given key was found at index:%dn", index);
     
        return 0;
    }

    Got Something To Say:

    Your email address will not be published. Required fields are marked *

    C
    } 239 queries in 0.338 seconds.