/*************************************************************
* Section : 15
* Machine No. : N
* Roll No. : 19CS100XY
* Name : Aritra Hazra
* Assignment No : 11a
* Description : Arbitrary Bi-partition Search in Ordered Array
**************************************************************/

#include <stdio.h>
#define MAX 100000

int BiPartitionSearch(int A[], int v, int a, int b, int low, int high)
{
    int pivot;
    if (low <= high)
    {
        pivot = low + a*(high-low)/b; /* findind a/b bi-partition point */
        if(A[pivot] > v) /* element may reside in the left part */
            return BiPartitionSearch (A,v,a,b,low,pivot-1);
        else if (A[pivot] < v) /* element may reside in the right part */
            return BiPartitionSearch (A,v,a,b,pivot+1,high);
        else /* element found at partition point */
            return pivot;
    }
    else /* element not found */
        return -1;
}

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

    /* 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 Bi-Partition Ratio (in a/b format): ");
    scanf("%d/%d", &a, &b);
    if(a > b)
    {
        printf("Error: Numerator is MORE than Denominator!\n");
        return;
    }

    /* Bi-partition Search Procedure */
    loc = BiPartitionSearch(A,x,a,b,0,n-1);

    /* displaying the sorted (in ascending order) array */
    printf("The Sorted Array:");
    for(i=0; i<n; ++i)
    {
        printf(" %d,", A[i]);
    }
    printf("\n");
    /* 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;
}