A template for performing binary search.

binary-search.cpp

// Iterative: O(log(n)) time and O(1) space
// Recursive: O(log(n)) time and O(log(n)) space

template <typename T>
int binarySearchIterative(std::vector<T> arr, T target) {
	int left = 0, right = arr.size()-1;
	while (left <= right) {
		int mid = left + ((right-left) / 2);
		if (target == arr[mid]) {
			return mid;
		} else if (target < arr[mid]) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return -1;
}

template <typename T, int N>
int binarySearchIterative(T arr[], T target) {
	int left = 0, right = N - 1;
	while (left <= right) {
		int mid = left + ((right-left) / 2);
		if (target == arr[mid]) {
			return mid;
		} else if (target < arr[mid]) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return -1;
}

template <typename T>
int binarySearchHelper(std::vector<T> arr, int left, int right, T target) {
	if (left >= right) return -1;
	int mid = left + ((right-left) / 2);
	if (target == arr[mid]) {
		return mid;
	} else if (target < arr[mid]) {
		return binarySearchHelper(arr, left, mid-1, target);
	} else {
		return binarySearchHelper(arr, mid+1, right, target);
	}
}

template <typename T>
int binarySearchRecursive(std::vector<T> arr, T target) {
	return binarySearchHelperTwo(arr, 0, arr.size()-1, target);
}

template <typename T>
int binarySearchHelperTwo(T arr[], int left, int right, T target) {
	if (left >= right) return -1;
	int mid = left + ((right-left) / 2);
	if (target == arr[mid]) {
		return mid;
	} else if (target < arr[mid]) {
		return binarySearchHelperTwo(arr, left, mid-1, target);
	} else {
		return binarySearchHelperTwo(arr, mid+1, right, target);
	}
	return -1;
}

template <typename T, int N>
int binarySearchRecursiveTwo(T arr[], T target) {
	return binarySearchHelperTwo(arr, 0, N-1, target);
}

int arr[] = {1,4,9,13,25,32,61,100};
char carr[] = {'a','b','c','e','t','u','v','y'};

int arrSize = sizeof(arr) / sizeof(arr[0]);
vector<int> ve;
vector<char> ce;

for (int i=0; i < arrSize; i++) ve.push_back(arr[i]);
for (int i=0; i < sizeof(carr) / sizeof(carr[0]); i++) ce.push_back(carr[i]);

for (int v : ve) {
    cout << v << " ";
}
cout << endl;

// vector<int> input
cout << "Binary search for target 32: " << endl;
int targetIdxOne = binarySearchRecursive(ve, 32);
cout << "Found at index: " << targetIdxOne << endl;
cout << "arr[" << targetIdxOne << "] = " << arr[targetIdxOne] << endl;

// vector<char> input
cout << "Binary search for target 'e': " << endl;
int targetIdxFour = binarySearchIterative(ce, 'e');
cout << "Found at index: " << targetIdxFour << endl;
cout << "arr[" << targetIdxFour << "] = " << carr[targetIdxFour] << endl;

// int[] input
int targetIdxTwo = binarySearchRecursiveTwo<int, 8>(arr, 13);
cout << "Binary search for target 13: " << endl;
cout << "Found at index: " << targetIdxTwo << endl;
cout << "arr[" << targetIdxTwo << "] = " << arr[targetIdxTwo] << endl;

// char[] input
int targetIdxThree = binarySearchRecursiveTwo<char, 8>(carr, 'u');
cout << "Binary search for target 'u': " << endl;
cout << "Found at index: " << targetIdxThree << endl;
cout << "arr[" << targetIdxThree << "] = " << carr[targetIdxThree] << endl;

Std out:

1 4 9 13 25 32 61 100 
Binary search for target 32: 
Found at index: 5
arr[5] = 32
Binary search for target 'e': 
Found at index: 3
arr[3] = e
Binary search for target 13: 
Found at index: 3
arr[3] = 13
Binary search for target 'u': 
Found at index: 5
arr[5] = u