Write a program in C++ to implement two different searching techniques: - Linear

Question

Write a program in C++ to implement two different searching techniques:
- Linear search
- Binary search
on a set of integer values stored in a single dimension array. The user will provide as input the set of the integer values and the number they did like to search for, and the option for the search technique they did like to use. Based on these three inputs provided by the user, your program will output a success prompt and the array index at which the value was found; if the search was successful. Or it should prompt a "not found" message and an option to re-try the search.

Your program must be written using functions (worth 10 points).

Input case:

7,2,5,67,89,11,23,6,18,43

option: Linear Search
Search value: 16

option: Binary Search

Search Value: 11

Note: This is going to be a two weeks Lab. During Lab sessions we'll discuss:
- How to use arrays with functions (Week 1)

- The algorithms for linear (Week 1) and binary search (Week 2)

- How to sort an array (prerequisite to performing binary search) [Week 2]

Explanation / Answer

#include<iostream>
#include<iomanip>
#include<array>
#include<string>
#include<algorithm>
using namespace std;

int LinearSearch( const int [], int, int );

void sortArray(int array[], int elems)
{
   int temp;
   bool swap;
   do
   {
       swap = false;
       for (int count = 0; count < (elems - 1); count++)
       {
           if (array[count] > array[count + 1])
           {
               temp = array[count];
               // swap
               array[count] = array[count + 1];
               array[count + 1] = temp;
               swap = true;
           }
       }
   } while (swap);
}
void showArray(int array[], int elems)
{
   for (int count = 0; count < elems; count++)
       cout << array[count] << " ";
   cout << endl;
}

void LinearSearch()
{
   const int arraySize = 10;
   int a[arraySize] = {41, 67, 34, 0, 69, 24, 78, 58, 62, 64};

   int searchKey1 = 50;
   int searchKey2 = 64;

   for ( int i = 0; i < arraySize; i++)
       a[i] = 2 * i;
   //Searching for value 50
   {
       int index1 = LinearSearch(a, searchKey1, arraySize);

       if ( index1 != -1 )
           cout << " Linear search called for value 50 : value found at index " << index1 << endl;
       else
           cout << " Linear search called for value 50 : value not found !" << endl;
   }

   {
       int index2 = LinearSearch(a, searchKey2, arraySize);

       if ( index2 != -1 )
           cout << " Linear search called for value 64 : value found at index " << index2 << endl;
       else
           cout << " Linear search called for value 64 : value not found !" << endl;
   }
  
}
int binarySearch(int array[], int numElems, int value)
{
   int first = 0; // First array element
   int last = (numElems) - 1; // Last array element
   int middle; // Midpoint of search
   int position = -1; // Position of search value
   bool found = false; // Flag
   while (!found && first <= last)
   {
       middle = (first + last) / 2; // Calculate midpoint
       if (array[middle] == value) // If value is found
       {
           found = true;
           position = middle;
       }
       else if (array[middle] > value) // value is in lower half
           last = middle - 1;
       else
           first = middle + 1; // value is in upper half
   }
   return position;
}

int main()
{
   const int SIZE = 10;
   int values[SIZE] = {41, 67, 34, 0, 69, 24, 78, 58, 62, 64};
   cout << " The unsorted values are: ";
   showArray(values, SIZE);
   sortArray(values, SIZE);
   cout << " The sorted values are: ";
   showArray(values, SIZE);

   LinearSearch();
  
   const int size = 10;

   int c[size] = {41, 67, 34, 0, 69, 24, 78, 58, 62, 64};
   int results1, results2;
   int num1 = 50;
   int num2 = 64;
   {
       results1 = binarySearch(c, size, num1);
       if (results1 == -1)
           cout << " Binary search called for value 50 : value not found ! ";
       else
       {
           cout << " Binary search called for value 50 : value found at element " << results1;
           cout << endl;
       }
   }
   {
       results2 = binarySearch(c, size, num2);
       if (results2 == -1)
           cout << " Binary search called for value 64 : value not found ! ";
       else
       {
           cout << " Binary search called for value 64 : value found at element " << results2;
           cout << endl;
       }
   }
   return 0;
}
int LinearSearch( const int array[], int key, int sizeOfArray )
{
   for ( int j = 0; j < sizeOfArray; j++ )
       if ( array[ j ] == key ) // if found,
       return j; // return location of key
   return -1; // key not found
}]

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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