Question

2.11 lab: binary search template function

Answer 1

To implement a binary search template function, follow these steps and use the provided example.

Step-by-step explanation:

To implement a binary search template function, you can use the following steps:

1. Define the function with the appropriate template syntax and parameters.
2. Initialize two variables 'start' and 'end' to represent the range of the search.
3. Iterate while 'start' is less than or equal to 'end'.
4. Compute the middle index as the average of 'start' and 'end'.
5. Compare the middle element with the target value.
6. If the middle element is equal to the target value, return its index.
7. If the middle element is greater than the target value, update 'end' to 'mid - 1'.
8. If the middle element is less than the target value, update 'start' to 'mid + 1'.
9. If the loop ends without finding the target value, return -1.

Here's an example of a binary search template function in C++:

template<typename T>
int binarySearch(T arr[], int size, T target)
{
int start = 0;
int end = size - 1;
while (start <= end)
{
int mid = start + (end - start) / 2;
if (arr[mid] == target)
{
return mid;
}
else if (arr[mid] > target)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
}
return -1;
}