CS201 Data Structures  Binary Search Recursive Name: _________________________

main()
{ int a[9] = {10, 15, 21, 33, 40, 50, 70, 80, 91 };
int key, x;

cin>>key;
x = rBinarySearch( a, 0, 8, key);
cout<<x;
}
int rBinarySearch(int sortedArray[], int first, int last, int key)
{ // function:Searches sortedArray[first]..sortedArray[last]for key.
// returns: index of the matching element if it finds key,
// otherwise -(index where it could be inserted)-1.
// parameters:
// sortedArray in array of sorted (ascending) values.
// first, last in lower and upper subscript bounds
// key in value to search for.
// returns:
// index of key, or -insertion_position -1
// if key is not in the array.
int mid;
if (first <= last)
{ mid = (first + last) / 2; // compute mid point.
if (key == sortedArray[mid])
return mid; // found it.
else if (key < sortedArray[mid])
// Call ourself for the lower part of the array
return rBinarySearch(sortedArray, first, mid-1, key);
else
// Call ourself for the upper part of the array
return rBinarySearch(sortedArray, mid+1, last, key);
}
return -(first + 1); // failed to find key
}
Input Data   50
Var
a[0] = 10
a[1] = 15
a[2] = 21
a[3] = 33
a[4] = 40
a[5] = 50
a[6] = 70
a[7] = 80
a[8] = 91










Output
Input Data   12
Var
a[0] = 10
a[1] = 15
a[2] = 21
a[3] = 33
a[4] = 40
a[5] = 50
a[6] = 70
a[7] = 80
a[8] = 91





Output
Input Data   80
Var
a[0] = 10
a[1] = 15
a[2] = 21
a[3] = 33
a[4] = 40
a[5] = 50
a[6] = 70
a[7] = 80
a[8] = 91





Output



Input Data   21
Var
a[0] = 10
a[1] = 15
a[2] = 21
a[3] = 33
a[4] = 40
a[5] = 50
a[6] = 70
a[7] = 80
a[8] = 91





Output