int binSearch(int arr[], int lo, int hi, int x) { int q = (low + high) / 2; if(a
ID: 3663833 • Letter: I
Question
int binSearch(int arr[], int lo, int hi, int x)
{
int q = (low + high) / 2;
if(arr[q] <= x && arr[q + 1] > x){
return q + 1;
}
else if(arr[q] == x){
return binSearch(arr, q + 1, high, x);
}
else if(arr[q] > x){
return binSearch(arr, low, q - 1, x);
}
else if(arr[q] < x){
return binSearch(arr, q + 1, high, x);
}
}
Based on the above function, write an iterative algorithm (based on a while loop) that implements the specification. Then calculate (and explain your answer) the maximum number of iterations of the while loop, as a function of n. Finally, convert your iterative program into a program with a tail-recursive function (which is called from the main function).
Explanation / Answer
iterative algorithm
function binarySearch(a, value, left, right)
while left right
mid := floor((right-left)/2)+left
if a[mid] = value
return mid
if value < a[mid]
right := mid-1
else
left := mid+1
return not found
program
<<generic binary search with two template arguments>>=
template< typename T, typename IterT >
IterT generic_binary_search(IterT begin, IterT end, T target) {
IterT initial_end = end;
while (begin < end) {
IterT middle = begin + (end - begin - 1)/2;
if (target < *middle)
end = middle;
else if (*middle < target)
begin = middle + 1;
else
return middle;
}
return initial_end;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.