Question

Programing language C++

In this exercise you will explore the performance difference between sequential search and binary search. To do so write a program that performs the following tasks:

Prompt the user for a file containing 100,000 unsorted integers

Read those integers into an array

Prompt the user for a search item

Search for that item (using sequential search) and report the number of comparisons required.

Sort the array. Note that this might take a few minutes.

Search for that item again (using binary search) and report the number of comparisons required.

You will need to modify both of the search functions to report the number of comparisons that were made during the search.

Use your program and the file of 100,000 integers provided here to answer the six questions in the quiz.

Answer 1

I've added code to generate file to store random numbers

Code with comments

#include <bits/stdc++.h>

using namespace std;

int linear_search(int arr[], int n, int val) {  // sequentail search

    for (int i = 0; i < n; i++) {

        if (arr[i] == val) {

            return i + 1;

        }

    }

    return n;

}

int binary_search(int arr[], int n, int val) {  // binary search

    int start = 0, end = n - 1, cnt = 0;

    while (start <= end) {

        int mid = (start + end) / 2;

        cnt++;

        if (arr[mid] == val) return cnt;

        if (arr[mid] > val)

            end = mid - 1;

        else

            start = mid + 1;

    }

    return cnt;

}

int main() {

    /**** generate data ***/

    // fstream file;

    // file.open("numbers.txt", ios::out);

    // for (int i = 0; i < 100000; i++) {

    //     file << rand() % 10000 << " ";

    // }

    // file.close();

    string filename;

    cout << "Enter file name containing numbers: ";

    cin >> filename;

    fstream file;

    file.open(filename);

    int arr[100000], n = 0, num;

    while (file >> num) arr[n++] = num;  // read into array

    cout << "Enter number to search: ";

    cin >> num;

    cout << "Comparisons required in sequential search: "

         << linear_search(arr, n, num) << endl;

    sort(arr, arr + n);  // sort array

    cout << "Enter number to search: ";

    cin >> num;

    cout << "Comparisons required in sequential search: "

         << binary_search(arr, n, num) << endl;

}