#include <iostream>
using namespace std;
 
static const int SIZE = 10;
 
int search(int arr[], int target, int startIndex, int endIndex) 
{
	if (startIndex > endIndex) return -1;
 
	int midIndex = (startIndex + endIndex) / 2;
 
	if (target == arr[midIndex])
		return midIndex;
	else if (target < arr[midIndex])
		search(arr, target, startIndex, midIndex-1);
	else 
		search(arr, target, midIndex+1, endIndex);
}
 
int main() {
	int arr[SIZE] = {1,2,3,4,5,6,7,8,9,10};
 
	cout << "3 is at index: " << search(arr, 3, 0, SIZE-1) << endl;
	// cout << "11 is at index: " << search(arr, 11, 0 , SIZE-1) << endl;
 
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RhdGljIGNvbnN0IGludCBTSVpFID0gMTA7CgppbnQgc2VhcmNoKGludCBhcnJbXSwgaW50IHRhcmdldCwgaW50IHN0YXJ0SW5kZXgsIGludCBlbmRJbmRleCkgCnsKCWlmIChzdGFydEluZGV4ID4gZW5kSW5kZXgpIHJldHVybiAtMTsKCglpbnQgbWlkSW5kZXggPSAoc3RhcnRJbmRleCArIGVuZEluZGV4KSAvIDI7CgoJaWYgKHRhcmdldCA9PSBhcnJbbWlkSW5kZXhdKQoJCXJldHVybiBtaWRJbmRleDsKCWVsc2UgaWYgKHRhcmdldCA8IGFyclttaWRJbmRleF0pCgkJc2VhcmNoKGFyciwgdGFyZ2V0LCBzdGFydEluZGV4LCBtaWRJbmRleC0xKTsKCWVsc2UgCgkJc2VhcmNoKGFyciwgdGFyZ2V0LCBtaWRJbmRleCsxLCBlbmRJbmRleCk7Cn0KCmludCBtYWluKCkgewoJaW50IGFycltTSVpFXSA9IHsxLDIsMyw0LDUsNiw3LDgsOSwxMH07CgoJY291dCA8PCAiMyBpcyBhdCBpbmRleDogIiA8PCBzZWFyY2goYXJyLCAzLCAwLCBTSVpFLTEpIDw8IGVuZGw7CgkvLyBjb3V0IDw8ICIxMSBpcyBhdCBpbmRleDogIiA8PCBzZWFyY2goYXJyLCAxMSwgMCAsIFNJWkUtMSkgPDwgZW5kbDsKCn0=