Implement recursive binary search using the following function prototype:

int binarySearch(const int A[], int left, int right, int e)

The function returns the index of e in A if found between left and right inclusive, or 1 if not found. It assumes the array A is sorted.

Binary search takes advantage of the ordered array property: it checks whether the middle element is equal to e, and if it is, it returns the middle elements index. Otherwise, if e is smaller than the middle element it returns the result of binary search on the left part of the array (between left and mid-1). Otherwise, if e is larger than the middle element it returns the result of the binary search on the right part of the array (between mid+1 and right). Finally, if element e is not between left and right, then binarySearch returns 1.

Implement binary search recursively in a separate function and test it by calling it from main. Remember that such functions can run into an infinite recursion if you do not provide appropriate base cases.