Assignment: Searching | DSA in C++ - Software Development PDF Download

Instructions

• This assignment consists of questions related to searching algorithms in C++.
• The assignment includes Multiple Choice Questions (MCQs), High Order Thinking Questions (HOTS), Fill in the Blanks, True/False, and Hands-On Questions.
• There are 5 questions for each category, with a mix of difficulty levels.
• At the end of the worksheet, you will find detailed answers to all the questions.

MCQs

Q.1. Which of the following is an advantage of linear search over binary search?
(a) Linear search has a lower time complexity than binary search.
(b) Linear search does not require sorted data.
(c) Linear search is more efficient for large datasets.
(d) Linear search has a logarithmic time complexity.
Ans. (b)

Q.2. In binary search, the array must be:
(a) Sorted in ascending order
(b) Sorted in descending order
(c) Unsorted
(d) None of the above
Ans. (a)

Q.3. The time complexity of binary search is:
(a) O(1)
(b) O(n)
(c) O(log n)
(d) O(n log n)
Ans. (c)

Q.4. Which of the following is a disadvantage of linear search?
(a) It cannot be implemented recursively.
(b) It has a higher time complexity than binary search.
(c) It requires the array to be sorted.
(d) It is not suitable for large datasets.
Ans. (b)

Q.5. The midpoint formula used in binary search is:
(a) mid = (low + high) / 2
(b) mid = low + (high - low) / 2
(c) mid = high - (high - low) / 2
(d) mid = (low - high) / 2
Ans. (b)

HOTS

Q.1. Write a C++ function to perform linear search in an integer array. The function should return the index of the target element if found, or -1 if not found.

int linearSearch(int arr[], int size, int target) {

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

        if (arr[i] == target)

            return i;

    }

    return -1;

}

Q.2. Write a C++ function to perform binary search in a sorted integer array. The function should return the index of the target element if found, or -1 if not found.

int binarySearch(int arr[], int size, int target) {

    int low = 0;

    int high = size - 1;

    while (low <= high) {

        int mid = low + (high - low) / 2;

        if (arr[mid] == target)

            return mid;

        else if (arr[mid] < target)

            low = mid + 1;

        else

            high = mid - 1;

    }

    return -1;

}

Q.3. Consider a scenario where you are given a sorted array of strings and you need to search for a particular string. Which searching algorithm would you choose, linear search or binary search? Justify your answer.

Binary search would be chosen for searching a particular string in a sorted array of strings. Binary search is efficient for sorted data, and since the array of strings is sorted, binary search can provide faster results compared to linear search.

Q.4. Can binary search be applied to a linked list? Explain why or why not.

No, binary search cannot be applied directly to a linked list. Binary search relies on random access to elements, which is not available in a linked list. Binary search requires accessing the middle element of the search range, which is not feasible in a linked list without traversing the list from the beginning.

Q.5. In binary search, what happens if the target element is not present in the array?

If the target element is not present in the array, binary search will eventually narrow down the search range until the low index becomes greater than the high index. At this point, the search will terminate, and the function will return -1 to indicate that the target element was not found.

Fill in the Blanks

1. Linear search has a time complexity of __________.
Ans. O(n)

2. Binary search requires the array to be __________.
Ans. Sorted in ascending order

3. The _________ search algorithm is used when the data is sorted and evenly distributed.
Ans. Binary

4. In binary search, the _________ value is compared with the target element to determine the next search range.
Ans. Midpoint

5. Linear search is also known as _________ search.
Ans. Sequential

True/False

1. Linear search is a recursive algorithm.
Ans. False

2. Binary search can only be applied to sorted arrays.
Ans. True

3. Binary search has a time complexity of O(log n).
Ans. True

4. Linear search is more efficient than binary search for large datasets.
Ans. False

5. Binary search always finds the target element if it is present in the array.
Ans. False

Hands-On

Q.1. Implement a C++ program to perform linear search in an array of floating-point numbers. The program should take user input for the target element and display whether it is found or not.

#include <iostream>

using namespace std;

bool linearSearch(float arr[], int size, float target) {

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

        if (arr[i] == target)

            return true;

    }

    return false;

}

int main() {

    int size;

    cout << "Enter the size of the array: ";

    cin >> size;

    float arr[size];

    cout << "Enter the elements of the array: ";

    for (int i = 0; i < size; i++)

        cin >> arr[i];

    float target;

    cout << "Enter the target element: ";

    cin >> target;

    if (linearSearch(arr, size, target))

        cout << "Element found!" << endl;

    else

        cout << "Element not found." << endl;

    return 0;

}

Q.2. Implement a C++ program to perform binary search in a sorted array of characters. The program should take user input for the target character and display its index if found, or a message indicating it is not present.

#include <iostream>

using namespace std;

int binarySearch(char arr[], int size, char target) {

    int low = 0;

    int high = size - 1;

    while (low <= high) {

        int mid = low + (high - low) / 2;

        if (arr[mid] == target)

            return mid;

        else if (arr[mid] < target)

            low = mid + 1;

        else

            high = mid - 1;

    }

    return -1;

}

int main() {

    int size;

    cout << "Enter the size of the array: ";

    cin >> size;

    char arr[size];

    cout << "Enter the elements of the array: ";

    for (int i = 0; i < size; i++)

        cin >> arr[i];

    char target;

    cout << "Enter the target character: ";

    cin >> target;

    int index = binarySearch(arr, size, target);

    if (index != -1)

        cout << "Character found at index " << index << endl;

    else

        cout << "Character not found." << endl;

    return 0;

}

Q.3. Write a C++ function to perform binary search in a recursive manner. The function should take parameters for the array, target element, low index, and high index. It should return the index of the target element if found, or -1 if not found.

#include <iostream>

using namespace std;

int recursiveBinarySearch(int arr[], int target, int low, int high) {

    if (low > high)

        return -1;

    int mid = low + (high - low) / 2;

    if (arr[mid] == target)

        return mid;

    else if (arr[mid] < target)

        return recursiveBinarySearch(arr, target, mid + 1, high);

    else

        return recursiveBinarySearch(arr, target, low, mid - 1);

}

int main() {

    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    int size = sizeof(arr) / sizeof(arr[0]);

    int target;

    cout << "Enter the target element: ";

    cin >> target;

    int index = recursiveBinarySearch(arr, target, 0, size - 1);

    if (index != -1)

        cout << "Element found at index " << index << endl;

    else

        cout << "Element not found." << endl;

    return 0;

}

Q.4. Implement a C++ program to demonstrate the working of linear search and binary search on an array of integers. The program should generate a random array and perform both searches on the same array, displaying the results.

#include <iostream>

#include <cstdlib>

using namespace std;

void linearSearch(int arr[], int size, int target) {

    bool found = false;

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

        if (arr[i] == target) {

            cout << "Linear Search: Element found at index " << i << endl;

            found = true;

            break;

        }

    }

    if (!found)

        cout << "Linear Search: Element not found." << endl;

}

int binarySearch(int arr[], int size, int target) {

    int low = 0;

    int high = size - 1;

    while (low <= high) {

        int mid = low + (high - low) / 2;

        if (arr[mid] == target)

            return mid;

        else if (arr[mid] < target)

            low = mid + 1;

        else

            high = mid - 1;

    }

    return -1;

}

int main() {

    const int SIZE = 10;

    int arr[SIZE];

    srand(time(0));  // Seed the random number generator

    cout << "Array: ";

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

        arr[i] = rand() % 100;  // Generate random numbers between 0 and 99

        cout << arr[i] << " ";

    }

    cout << endl;

    int target;

    cout << "Enter the target element: ";

    cin >> target;

    linearSearch(arr, SIZE, target);

    int binaryIndex = binarySearch(arr, SIZE, target);

    if (binaryIndex != -1)

        cout << "Binary Search: Element found at index " << binaryIndex << endl;

    else

        cout << "Binary Search: Element not found." << endl;

    return 0;

}

Q.5. Consider a scenario where you have an array of sorted strings and you need to search for a particular string using binary search. Implement a C++ program to perform this task. The program should take user input for the target string and display whether it is found or not.

#include <iostream>

#include <string>

using namespace std;

int binarySearch(string arr[], int size, string target) {

    int low = 0;

    int high = size - 1;

    while (low <= high) {

        int mid = low + (high - low) / 2;

        if (arr[mid] == target)

            return mid;

        else if (arr[mid] < target)

            low = mid + 1;

        else

            high = mid - 1;

    }

    return -1;

}

int main() {

    const int SIZE = 5;

    string arr[SIZE] = {"apple", "banana", "grape", "orange", "strawberry"};

    string target;

    cout << "Enter the target string: ";

    cin >> target;

    int index = binarySearch(arr, SIZE, target);

    if (index != -1)

        cout << "String found at index " << index << endl;

    else

        cout << "String not found." << endl;

    return 0;

}