Binary search algorithm that can be used to search a string vector object | MindTap Computing for Malik's C++ Programming 8th Edition

Introduction:

Write a version of the binary search algorithm that can be used to search a string vector object. Also, write a program to test your algorithm.

Source: MindTap Computing for Malik's C++ Programming From Problem Analysis to Program Design, 8th Edition, [Instant Access] (8th)-Malik, chapter 16, programming exercises 15.

Solved!

The objective of the programming exercise is to implement a binary search algorithm to find string in vector<string> object which is sorted by selection sort.

Program Plan:

· Define header section.

· Define selectionSort() function.

· Define binSearch() function which takes array arr and string s.

o Declare left = 0 and right = arr.size() -1.

o While loop left <= right.

§ Declare m = (left + right) / 2.

§ If arr[m] == s.

· Found element s in arr at index m, return m.

§ Else if arr[m] < s.

· Set left = m + 1.

§ Else if arr[m] > s.

· Set right = m - 1.

o Return -1 if not return any value in the while loop.

· Define main() function.

o Declare n ask to take user input.

o Declare vector<string> arr of size n.

o Take user input to fill arr.

o Declare string s and take user input for s.

o Sort array using selectionSort()

o Print sorted array

o Find index p using binSearch() function call.

o Print the result using if-else

Program:

// objective of programming exercise is to implement binary search
// algorithm to find string in vector<string> object which is sorted by selection sort.

#include <iostream>
#include <vector>

using namespace std;

// selectionSort() which take vector<string> pass by reference and sort it in ascending order.
void selectionSort(vector<string> &arr)
{
    // array size.
    int n = arr.size();
    // for each index i from 0 to n-2.
    for (int i = 0; i < n - 1; i++)
    {
        // find minimum element index from i to n-1.
        int min_j = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[min_j])
            {
                min_j = j;
            }
        }
        // swap it with i index element.
        swap(arr[i], arr[min_j]);
    }
}

// binSeach() which takes vector<string> arr as pass by reference and s string.
// and return index of s in arr.
// if not found return -1.
int binSeach(vector<string> &arr, string s)
{
    // set left = 0 and right = arr size - 1.
    int left = 0;
    int right = arr.size() - 1;
    // while left is less or equal right.
    while (left <= right)
    {
        // find mid point m
        int m = (left + right) / 2;
        // if arr[m] is equal to s.
        if (arr[m] == s)
        {
            // return m.
            return m;
        }
        // else if arr[m] is less than s.
        else if (arr[m] < s)
        {
            // set left equal to m+1.
            left = m + 1;
        }
        // else if arr[m] is greate than s.
        else if (arr[m] > s)
        {
            // set right equal to m-1.
            right = m - 1;
        }
    }

    // return -1 if not found.
    return -1;
}

// driver code.
int main()
{
    // ask n array size.
    int n;
    cout << "Enter array size:";
    cin >> n;

    // fill vector<string> arr of n size by user input.
    vector<string> arr(n);
    cout << "Enter " << n << " number of strings:" << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    // taking word to search in vector.
    string s;
    cout << "Enter word you want to seach for in sorted vector:";
    cin >> s;

    // sort array.
    selectionSort(arr);
    // print sorted array.
    cout << "Vector after sort:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << ", ";
    }
    cout << endl;

    // find p index using function call.
    int p = binSeach(arr, s);
    // if p is -1.
    if (p == -1)
    {
        // not found.
        cout << "Entered word not found in vector." << endl;
    }
    else
    {
        // else print p index.
        cout << "Entered word found in vector at index " << p << endl;
    }

    return 0;
}