DS searching techniques or algorithms with complexity

Unknown 11:31
In computer science, a search algorithm is an algorithm that retrieves information in a computer's storage. Search algorithms can be classified based on their mechanism of searching.

1. LINEAR SEARCH

Linear search or sequential search is a method for finding a particular value in a list that checks each element in sequence until the desired element is found or the list is exhausted. The list need not be ordered.
ITERATIVE LINEAR SEARCH FUNCTION
This function returns the index of searching element if the searching element is found and it returns -1 if the searching element is not found or the array is empty.
Here, key is the searching element, lb is the first index and ub is the last index of array A[].

int iterativeLS(int A[], int key, int lb, int ub)
{
   int i,mid,flag=0;
   if (ub < lb)
   {
       return -1; // array is empty, so return value -1
   }
   for (i=lb;i<=ub;i++)
   {
      if (A[i] == key)
      {
         flag=1; break;
      }
   }
   if (flag==1 ) 
   {
      return i;   // key found at index i
   }
   else 
   {
      return -1;   // key was not found, so return value -1
   }
}

2. BINARY SEARCH

The binary search algorithm begins by comparing the target value to the value of the middle element of the sorted array. If the target value is equal to the middle element's value, then the position is returned and the search is finished. If the target value is less than the middle element's value, then the search continues on the lower half of the array; or if the target value is greater than the middle element's value, then the search continues on the upper half of the array. This process continues, eliminating half of the elements, and comparing the target value to the value of the middle element of the remaining elements ¬ until the target value is either found (and its associated element position is returned), or until the entire array has been searched (and "not found" is returned).

ITERATIVE BINARY SEARCH FUNCTION
This function returns the index of searching element if the searching element is found and it returns -1 if the searching element is not found or the array is empty.
Here, key is the searching element, lb is the first index and ub is the last index of array A[].

int iterativeBS(int A[], int key, int lb int ub)
{
   while (lb <= up)
   {
      int mid = (ub-lb)/2;   // calculate the midpoint roughly
      if (A[mid] == key)
      {
         return mid;   // key found at index mid
      }
      else if (A[mid] < key)   // determine which subarray to search
      {
         lb = mid + 1;   // change min index to search upper subarray
      }
      else
      {
         ub = mid - 1;   // change max index to search lower subarray
      }
   }
   return -1;   // key was not found
}


RECURSIVE BINARY SEARCH FUNCTION
This function returns the index of searching element if the searching element is found and it returns -1 if the searching element is not found or the array is empty.
Here, key is the searching element, lb is the first index and ub is the last index of array A[].

int recursiveBS(int A[ ] , int key, int lb, int ub)
{
   if (ub < lb)   // test if array is empty
   {
      return -1;     // set is empty, so return value -1.
   }
   else
   {
      int mid = (ub-lb) /2; // calculate midpoint to cut set in half
      // three‐way comparison
      if (A[ mid] > key)   // key is in lower subset
      {
         return recursiveBS (A, key, lb, mid - 1) ;
      }
      else if (A[ mid] < key) // key is in upper subset
      {
         return recursiveBS (A, key, mid + 1, ub) ;
      }
      else       // key has been found
      {
         return mid;
      }
   }
}
Tags: