You will be converting the binary search function into a template version . And

Question

You will be converting the binary search function into a template version. And this template version of binary search function should be able to work with different data types. IWe are going to use both std::list and std::vector.

Note: Since now the template binary search function is generic for both list and vector, when you traverse the elements inside a list or a vector using iterators, you should probably use std::advance and std::distance instead of the +/- and +=/-= operators, because the latter only work with random access iterators (although std::advance(iterator, 1) and ++iterator do the same thing).

Note:  Don't forget to #include <list> and #include <algorithm> if you are going to use std::list, std::advance and std::distance.

Here is the example output:

For vector v = {1, 2, 5, 7, 9, 13, 15, 18} and list l = {1, 2, 3, 4, 5, 6, 7, 8}:

./Lab8

7 is in the 4th position in the vector.

7 is in the 7th position in the list.

Explanation / Answer

#include     

#include    

#include       

#include

int main () {

std::list first;                                // empty list of ints

std::list second (8,100);

std::list third (second.begin(),second.end()); // iterating through second

std::list fourth (third);                       // a copy of third

int li[] = {1, 2, 3, 4, 5, 6, 7, 8}:

std::vector v{1, 2, 5, 7, 9, 13, 15, 18}; // use of vector

auto n = std::distance(v.begin(), v.end());

// using default comparison:

std::sort (v.begin(), v.end());

std::cout << "looking for 7... ";

if (binary_search (v, n, 7))

    std::cout << "found! ";

else

    std::cout << "not found. ";

std::list fifth (li, li + sizeof(li) / sizeof(int) );

std::cout << "looking for 7... ";

for (std::list::iterator it = fifth.begin(); it != fifth.end(); it++)

    std::cout << *it << ' ';

std::cout << ' ';

   return 0;

}

int binarySearch(T a[], int n, T& x)

{

            int left = 0;                       // left end of segment

            int right = n - 1;                  // right end of segment

            while (left <= right)

            {

                        int middle = (left + right)/2;   // middle of segment

                        if (x == a[middle]) return middle;

                        if (x > a[middle]) left = middle + 1;

                        else right = middle - 1;

            }

            return -1; // x not found

}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.