/*******************************************
* Section : 15
* Machine No. : N
* Roll No. : 19CS100XY
* Name : Aritra Hazra
* Assignment No : 11b
* Description : d-ary Search via d-partition
********************************************/

#include <stdio.h>
#define MAX 100000

int DarySearch(int A[], int v, int d, int low, int high)
{
    int idx=-1, pivot, p;
    if (low <= high)
    {
        for(p=1; p<d; ++p)
        {
            pivot = low + p*(high-low)/d; /* findind p/d partition point */
            if(A[pivot] > v) /* element may reside in the leftmost partition */
            {
                idx = DarySearch (A,v,d,low,pivot-1);
                break;
            }
            else if (A[pivot] < v) /* element may reside in the right partitions */
            {
                low = pivot+1;
            }
            else /* element found at p/d partition point */
            {
                idx = pivot;
                break;
            }
        }
        if(p==d) /* element may reside in the rightmost partition */
        {
            idx = DarySearch (A,v,d,low,high);
        }
    }
    return (idx);
}

int main()
{
    int A[MAX], x, loc, n, i, d;

    /* taking n-element sorted integer array input from user */
    printf("Enter Number of Elements: ");
    scanf("%d", &n);
    if(n==0) /* no element in array case */
    {
        printf("Array has NO element!\n");
        return;
    }
    printf("Enter %d Integer Elements in Ascending-Order (Sorted): ", n);
    for(i=0; i<n; ++i)
    {
        scanf("%d", &A[i]);
    }
    /* taking from user the element to be searched */
    printf("Enter the Element to be Searched: ");
    scanf("%d", &x);
    /* taking from user the arbitrary bi-partition point/ratio */
    printf("Enter the Expected Number of Partitions: ");
    scanf("%d", &d);
    if(d > n)
    {
        printf("Error: Requested Number of Partitions are MORE than Array Size!\n");
        return;
    }

    /* Triparted Ternary Search Procedure */
    loc = DarySearch(A,x,d,0,n-1);

    /* displaying the location where the searched element resides in the sorted (in ascending order) array */
    if(loc == -1)
    {
        printf("The Searched Element ( %d ) is NOT Found in the Sorted Array!\n", x);
    }
    else
    {
        printf("The Searched Element ( %d ) resides in %d-th Index of the Sorted Array!\n", x, loc);
    }

    return 0;
}