Description

The purpose of this challenge is to implement linear and binary searches on an array.

 Requirements

1. Define a string array in main() as below

   string text[25] = { "winter", "radius", "arthritis", "sponge", "rotation", "brandy", "radium", "crank", "ginger", "ankle", "cooler", "cranium", "potato", "receipt", "keratin", "stool", "termite", "dynamite", "singing", "banker", "thrifty", "longer", "tattoo", "rations", "being"};

2. Write a function int find_item_linear(string items[], string item, int size). Using a linear or sequential search, this function will return the index of item if it is found in items. If the item is not found, return -1. size represents the size of the array.
3. Write a function void sort(string items[], int size). This function will sort items in increasing order. Use any sorting algorithm you like.
4. Write a function int find_items_binary(string items[], string item, int size). Using a binary search, this function will return the index of item if it is found in items. Use a non-recursive approach to perform the binary search. If the item is not found, return -1.
5. Write a function int find_matches(string items[], string pattern, int size, string matches[]). This function will search items looking for strings that contain pattern. This function returns a count of the number of matching strings. Use the matches array to store the matching strings. The sample code below shows how to check if a string contains another string

     // how to search strings for partials 
     // where you're searching for needle in the haystack
     // you need to include <string>
   
     string haystack = "amazon";
     string needle = "az";
     std::size_t found = haystack.find(needle);
     if (found != std::string::npos)
       cout << "Found " << needle << endl;
   

6. In main(), display a menu that asks the user to either 1) search for a word using linear, 2) search for a word using binary search, and 3) search for a partial string.
7. Use the functions created above to satisfy the menu requirements.

Partial main()

#include <iostream>
#include <string>

int main()
{
  string text[25] = { "winter", "radius", "arthritis", "sponge", "rotation", "brandy", "radium", "crank", "ginger", "ankle", "cooler", "cranium", "potato", "receipt", "keratin", "stool", "termite", "dynamite", "singing", "banker", "thrifty", "longer", "tattoo", "rations", "being"};

  sort(text, 25);  // needed for binary search to work

  cout << "1- Search for a word using linear" << endl;
  cout << "2- Search for a word using binary" << endl;
  cout << "3- Search for a partial string" << endl;

  return 0;
}

Sample Interaction

1- Search for a word using linear
2- Search for a word using binary
3- Search for a partial string
Action: 1

Enter string: banker
Found banker

1- Search for a word using linear
2- Search for a word using binary
3- Search for a partial string
Action: 1

Enter string: zebra
zebra was not found

1- Search for a word using linear
2- Search for a word using binary
3- Search for a partial string
Action: 2

Enter string: banker
Found banker

1- Search for a word using linear
2- Search for a word using binary
3- Search for a partial string
Action: 2

Enter string: zebra
zebra was not found

1- Search for a word using linear
2- Search for a word using binary
3- Search for a partial string
Action: 3

Enter partial search term: ra
Found brandy cranium crank keratin radium radius rations 

1- Search for a word using linear
2- Search for a word using binary
3- Search for a partial string
Action: 3

Enter partial search term: zz
Found no matches

LEGEND
PROGRAM OUTPUT
USER INPUT
FROM INPUT

CATALOG ID: CPP-CHAL0058