Thanks to @Josay for pointing out an infinite loop that I didn't know about in the original code.
Updated Code after answer by William Morris
static int bin_search(const int arr[], int min, int max, const int element)
{
/*
Searches for an element in the array arr
Returns index of element if present else returns -1
*/
if (min > max){
return -1;
}
//Don't change this assignment of mid. It avoids overflow
int mid = min + (max - min)/2;
if (arr[mid] > element){
return bin_search(arr, min + 1, mid, element);
}
else if (arr[mid] < element){
return bin_search(arr, mid, max - 1, element);
}
return mid;
}
After Ruds answer and some thinking I came up with a solution that uses the same number of comparison as his answer but doesn't have the flaw, of accessing uninitialized memory in case the user isn't careful, which he had pointed out.
I broke up the bin_search function into 2 parts. The main bin_search takes care of uninitialized memory and then tail-recursive procedure bin_proc is started. It adds 1 comparison for any search(not for each recursive call). The complexity becomes the same as suggested in Ruds' answer without that flaw.
static int bin_proc(const int arr[], int min, int max, int element)
{
if (min >= max){
return arr[max] == element ? max : -1;
}
//Don't change this assignment of mid. It avoids overflow
int mid = min + (max - min)/2;
if (arr[mid] < element) {
return bin_proc(arr, mid + 1, max, element);
}
else {
return bin_proc(arr, min, mid, element);
}
}
int bin_search(const int arr[], int length, int element)
{
/*
Searches for an element in the array arr
If present returns index else returns -1
*/
if (length < 1){
return -1;
}
return bin_proc(arr, 0, length - 1, element);
}
