/**
 * @file binary_search.cpp
 * @author Shirish Reddy <shirishreddy89@gmail.com>
 * 
 * Binary Search - searches for a value if present in the array returns the index of it.
 */

#include <iostream>

using namespace std;

/**
 * Search_inner - searches for the value in the given bounds , start and end. 
 *
 * @param value to be searched
 * @param Array to be looked
 * @param start and end bounds
 * @return returns the index if the value is found else return -1
 */
int search_inner(int val, int *a, int start, int end)
{
	if(start == end) {
		return -1;
	}
	int len = end - start;
	if(len == 1){
		if(val == a[start]){
			cout<<start<<endl;
			return start;
			}
		else
			return -1;
	}
	int mid = (start+end)/2;
	if(val == a[mid]){
		return mid;
		}
	else if(val < a[mid])
		return search_inner(val, a, start, mid);
	else if(val > a[mid])
		return search_inner(val, a, mid+1, end);
	return -1;
}

/**
 * binary_search is wrapper function for search_inner presenting search_inner with bounds
 *
 * @param Array to be search in 
 * @param value to be searched for
 * @param length of the array
 * @return returns the index of the value if found else -1
 */
int binary_search(int *a, int val, int len){
	return search_inner(val, a, 0, len);
}
int main(){
	int A[] = {1,2,3,4,5,6,7,8,9,10,11};
	cout<<binary_search(A,9,11);
	return 0;
}
		

8