/*A recursive function search that checks whether q is present in the array 
The array is sorted and hence a new way of searching will be used. First, the
element to be searched q is compared with the middle element of the array. The
middle element is at the index mid = (start + end) / 2. Now there are three
possibilities:

(a) a[mid] is q. Return mid.
(b) a[mid] < q. Since the array is sorted, q cannot lie on the left side of the
array. So the part of the array now needs to be searched is from mid + 1 to
end.
(c) a[mid] > q. Since the array is sorted, q cannot lie on the right side of
the array. So the part of the array now needs to be searched is from start to
mid - 1.

Author:rahule@cse.iitk.ac.in
*/

#include<stdio.h>
//Fuction Declaration
int search(int a[], int q, int start, int end);

int main()
{	int a[10];
    int q,i;
    printf("\nPlease input 10 distinct numbers in ascending order ");
    for(i=0;i<10;i++)
      { scanf("%d",&a[i]);
        //Checking whether the array entered is in ascending order and checking whether there are any duplicates 
        if(i!=0  && a[i]<=a[i-1])
          { printf("\nInvalid input .Your input needs to be distinct and in ascending order.\nPlease re-enter your last input ");
            i--;
          }
      }
	printf("\nPlease enter the element to be searched for ");
	scanf("%d",&q);
	i=search(a,q,0,9);
	if(i==-1)
	  {  printf("\nElement Not found ");
	  }
	else
	   printf("\nElement found at index %d ",i);
	return 0;
}	

int search(int a[], int q, int start, int end)
{	int mid;
    mid=(start+end)/2; 
    //checking for base condition ie when there is only one element in the subportion where search is carried out
    if(mid==start&&start!=end-1)
      {if(a[mid]==q)
         {return mid;
         }
       else return -1;
      }  
      	      
	if(a[mid]==q)
	  return mid;
	//search carried out recursively on the 1st half of the array if the mid element is greater than the element searched for  
	if(a[mid]>q)
	  return search(a,q,start,mid-1);
	//search carried out recursively on the second half of the array if the mid element is less than the element searched for
	else
	  return search(a,q,mid+1,end);  
}