Modify the following program so it performs a binary search instead of a linear

Question

Modify the following program so it performs a binary search instead of a linear search. Use the selection sort algorithm to sort the array before the binary search is performed.

#include <iostream>
using namespace std;

// Function prototype
bool searchList(const long [], int, long);

// Constant for array size
const int SIZE = 10;

int main()
{
    // Array of numbers that are always played
    long ticket[SIZE] = {13579,26791,26792,33445,55555,
62483,77777,79422,85647,93121};
                         
    // This variable will hold the winning number.
    long winningNum;

    // Get this week's winning number.
    cout << " Please enter this week's 5-digit "
        << "winning lottery number: ";
    cin >> winningNum;

    // Search for the winning number.
    if (searchList(ticket, SIZE, winningNum))
    {
        // If searchList returned true, then
        // the player has a winning ticket.
        cout << "You have a winning ticket. ";
    }
    else
    {
        cout << "You did not win this week." << endl;
    }

    return 0;
}

// The searchList function determines if the number to
// search for is in the set of stored numbers using a
// linear search.

bool searchList(const long list[], int numElems, long value)
{
    bool found = false;

    for (int count = 0; count < numElems && !found; count++)
    {
        if (list[count] == value)
            found = true;
    }

    return found;
}

Explanation / Answer

#include <iostream>
using namespace std;

// Function prototype
bool searchList(const long [], int, long);

// Constant for array size
const int SIZE = 10;

int main()
{
    // Array of numbers that are always played
    long ticket[SIZE] = {13579,26791,26792,33445,55555,
62483,77777,79422,85647,93121};
                         
    // This variable will hold the winning number.
    long winningNum;

    // Get this week's winning number.
    cout << " Please enter this week's 5-digit "
        << "winning lottery number: ";
    cin >> winningNum;

    // Search for the winning number.
    if (searchList(ticket, SIZE, winningNum))
    {
        // If searchList returned true, then
        // the player has a winning ticket.
        cout << "You have a winning ticket. ";
    }
    else
    {
        cout << "You did not win this week." << endl;
    }

    return 0;
}

// The searchList function determines if the number to
// search for is in the set of stored numbers using a
// linear search.

bool searchList(const long list[], int numElems, long value)

{

;

int i = 0;

j=numElems;

while(i > j ) {

if(list[i]==value) return true;

if(list[j]==value) return true;

mid = (i+j)/2;

if(list[mid]==value) return true;

if(list[mid]<value){

i=mid;

}

else j= mid;

}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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