Article 3: Searching Methods

 

Linear Search (Sequential Search)

Linear Search:

A linear search is the basic and simple search algorithm. A linear search searches an element or value from an array till the desired element or value is not found and it searches in a sequence order. It compares the element with all the other elements given in the list and if the element is matched it returns the value index else it return -1. Linear Search is applied on the unsorted or unordered list when there are fewer elements in a list.

Steps for Implementation:

Input: Array D, integer key

Output: first index of key in D, or -1 if not found

For i = 0 to last index of D:

if D[i] equals key:

return i

return -1

 

Source Code:

* Lab Assignment 2

Implement and Time Analysis of Linear and Binary search techniques

(1) Linear Search */

 

// importation of header files

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

 

//defined the linear search function

void linear_search(long [],long,long);

 

//defined the main function

void main()

{

    long arr[100000], i, num, n;

    clock_t start_time,end_time;

   

    // Taken the amount of elements for array creation from the users.

    printf("Enter the array size : ");

    scanf("%ld",&n);

   

    for(i=0; i<n; i++)

    {

        arr[i]=n-i;

    }

   

    // The element user wants to search in the list

    printf("Enter the number to be search : ");

    scanf("%ld",&num);

   

    //Initializing the time in clock in start variable

    start_time=clock();

   

    //arr is name of array, n is value of total elements, num is the element user wants to search

    linear_search(arr,n,num);

   

    //Finding the end time in clock and storing it into end_time variable

    end_time=clock()-start_time;

   

    //Time taken is the actual time taken in execution of linear search

    double time_taken=((double)end_time)/CLOCKS_PER_SEC;

    printf("\nlinear_search took %f seconds to execute \n",time_taken);

}

 

void linear_search(long arr[],long n,long num)

{

    int i;

    long c=0,pos;

    for(i=0; i<n; i++)

    {

        if(arr[i]==num)

        {

            c=1; // the value of c becomes 1 when you find the element

            pos=i+1; //position is considered i+1 because of 0 indexing

            break;

        }

    }

   

    if(c!=0) // whenever the value of c becomes 1, it means you have found the desired element.

    {

    printf(" %ld found at position %ld",num,pos);

    }

}

Binary Search

Binary Search:

Binary Search is applied on the sorted array or list. In binary search, we first compare the value with the elements in the middle position of the array. If the value is matched, then we return the value. If the value is less than the middle element, then it must lie in the lower half of the array and if it's greater than the element then it must lie in the upper half of the array. We repeat this procedure on the lower (or upper) half of the array. Binary Search is useful when there are large numbers of elements in an array.

Steps for Implementation/Algorithm:

A ← sorted array

n ← size of array

x ← value to be searched

 

Set lowerBound = 1

Set upperBound = n

 

while x not found

if upperBound < lowerBound

x does not exists.

 

set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

 

if A[midPoint] < x

set lowerBound = midPoint + 1

 

if A[midPoint] > x

set upperBound = midPoint - 1

 

if A[midPoint] = x

x found at location midPoint

 

end while

 

 

 

 

Source Code:

Implementation and time analysis techniques for searching techniques

(2) Binary Search. */

 

//Importation of Header files

#include<stdio.h>

#include <time.h>

 

// for performing binary search,it is must that all elements in array should be sorted

// defined the sorting function

void sort(long a[],long n)

{

  long i,j,temp;

  for(i=0;i<n;i++)

  {

    for(j=i;j<n;j++)

    {

       if(a[i]>a[j])

       {

         //swapping method for sorting the elements by assigning the value to temp variable

        temp=a[i];

        a[i]=a[j];

        a[j]=temp;

       }

    }

  }

}

 

//defined the binary search function

long binary_search(long p,long q,long k[],long x)

// p is lower bound, q is upper bound, k is sorted array and x is element we need to search

{

  long mid,loc;

// mid is the middle index for array and loc is location for array

 

  if(p>q)

// lower bound can not be greater than upper bound

    return -1;

  else

    mid=(p+q)/2;

// giving the indexing for middle element of array

 

  if(x<k[mid])

// if the wanted element is less than the element of middle index then the upper bound restricts to the lefter side from middle index

  {

    loc=binary_search(p,mid-1,k,x);

  }

  else if(x>k[mid])

  {

   loc=binary_search(mid+1,q,k,x);

// if the wanted element is greater than the element of middle index then the lower bound restricts to the right side from middle index

  }

 else

 {

   loc=mid;

//otherwise if the element found at middle index only, then it assigns the mid value to location

   return (loc+1);

// returns the index of wanted element.

 }

}

 

void main()

{

  long a[100000],n,i,x,loc;

  clock_t start_time,end_time;

 

  // taking the size of array from users

  printf("Enter the size of array:\n");

  scanf("%ld",&n);

 

 // for giving values to array indexes

  for (i = 0; i < n; i++)

  {

    a[i]=n-i;

  }

 

  //called the sorting function

  sort(a,n);

 

  // The element taken from user wants to search

  printf("Enter the element to search:\n");

  scanf("%ld",&x);

 

  // initializing the start clock time to variable start_time

  start_time=clock();

 

  // loc = location of element, 0 is lower bound,n-1 is upper bound,x is the element user needs to search,a is the sorted array

  loc=binary_search(0,n-1,a,x);

 

  // finding the end time after execution of operation

  end_time=clock()-start_time;

 

  //the total time of execution for operation of binary search

  double time_taken=((double)end_time)/CLOCKS_PER_SEC;

 

  printf("\n binary_search took %f seconds to execute \n",time_taken);

  printf("Location: %ld\n",loc);

}