Answer to Question #237504 in C for Aadi

Question

Design a recursive algorithm to search a sorted array a for an element x between a[low] and
a[high]. If no element is found it returns -1. Also, analyse the time and space complexity of your
algorithm.

Answer 1

# include<stdio.h>

int RecursiveSearch(int arr[], int size, int k)
{
    int loc;
    if (arr[size] == k)		return size;
    else if (size == -1)    return -1;
    else				    return (loc = RecursiveSearch(arr, size - 1, k));
}


int main()
{
    int size, index, key;
    int a[] = {2, 5, 11, 23, 34, 45, 56, 67, 78, 89};
    int count = 0;
    int i;
 
 	index = sizeof(a)/sizeof(a[0]);
    printf("\nInput List: ");
    for (i = 0; i < index; i++)       printf("%d\t", a[i]);
    printf("\nEnter the key to search: ");    scanf("%d", &key);
    while (index > 0)
    {
        index = RecursiveSearch(a, index - 1, key);
        if(index >=0) 
		{
			printf("Key found at position: %d\n", index + 1);
        	count++;			
		}
    }
    if (!count)
        printf("Key not found.\n");
    return 0;
}