Algorithms In Data Structure

Searching Algorithm

Linear Structure




static int search(int arr[], int n, int x)

    {

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

            // Return the index of the element if the element

            // is found

            if (arr[i] == x)

                return i;

        }

  

        // return -1 if the element is not found

        return -1;

    }










TimeComplexity - O(n) average

Space Complexity - O(1)







Binary Search







int binarySearch(int array[], int element, int low, int high) {

    if (high >= low) {
      int mid = low + (high - low) / 2;

      // check if mid element is searched element
      if (array[mid] == element)
        return mid;

      // Search the left half of mid
      if (array[mid] > element)
        return binarySearch(array, element, low, mid - 1);

      // Search the right half of mid
      return binarySearch(array, element, mid + 1, high);
    }

    return -1;
  }




Time Complexity: O(log N)
Auxiliary Space: O(1)










Ternary Search

int ternary_search(int l,int r, int x)
{
    if(r>=l)
    {
        int mid1 = l + (r-l)/3;
        int mid2 = r -  (r-l)/3;
        if(ar[mid1] == x)
            return mid1;
        if(ar[mid2] == x)
            return mid2;
        if(x<ar[mid1])
            return ternary_search(l,mid1-1,x);
        else if(x>ar[mid2])
            return ternary_search(mid2+1,r,x);
        else
            return ternary_search(mid1+1,mid2-1,x);

    }
    return -1;
}

Sorting Algorithm