C++ Coding Test Course, Finding Desired Integer

Hello! Welcome to the C++ coding test course together with you. Today’s topic is ‘Finding the Desired Integer’. This course will help you prepare for coding tests in C++. I will explain in detail the process of understanding the problem and finding the correct solution. This course is designed to be over 20,000 characters long.

Problem Description

You have an integer array arr and an integer target. Write a program that finds target in arr and returns its index. If target does not exist in arr, return -1. The length of the array can be up to 10^6. The array may not be sorted.

Input

arr = [2, 3, 4, 7, 11, 15, 20]
target = 7

Output

Result: 3

Problem Analysis

This problem involves finding a specific value in an array, which can be solved in various ways. The common methods are linear search and binary search. However, binary search is more efficient when the array is sorted. In this case, since the array is not sorted, we will use linear search to solve the problem.

Algorithm Choice

Since the problem provides an unsorted array, we will use linear search. Linear search is a simple algorithm that checks each element of the array one by one to find the desired value. The time complexity is O(n).

Linear Search Algorithm

The basic idea of linear search is as follows:

  1. Start from the first element of the array.
  2. Compare each element of the array sequentially until you find the desired integer.
  3. If found, return the index of that element.
  4. If not found by the end of the array, return -1.

Code Implementation

Now let’s implement the linear search algorithm in C++. I have written the code below:

#include <iostream>
#include <vector>

int findTarget(const std::vector<int> &arr, int target) {
    for (size_t i = 0; i < arr.size(); ++i) {
        if (arr[i] == target) {
            return i; // Target found, return index
        }
    }
    return -1; // Target not found
}

int main() {
    std::vector<int> arr = {2, 3, 4, 7, 11, 15, 20};
    int target = 7;

    int index = findTarget(arr, target);
    if (index != -1) {
        std::cout << "Result: " << index << std::endl;
    } else {
        std::cout << "Result: -1" << std::endl;
    }

    return 0;
}

Code Explanation

In the above code, the findTarget function takes the array and the value to find as input and returns that value found in the array.

  1. Access each element of the array through a for loop.
  2. Check if the current element is equal to target. If so, return the corresponding index.
  3. If not found after checking all elements, return -1 to indicate ‘not found’.

Performance Analysis

The time complexity of the above linear search algorithm is O(n). In the worst case, all elements of the array will need to be checked, so this performance occurs when n is the size of the array. The memory complexity is O(1).

Testing

Now let’s create some test cases to verify the validity of the algorithm.

Test Cases

  1. arr = [1, 2, 3, 4, 5], target = 3 -> Result: 2
  2. arr = [10, 20, 30, 40, 50], target = 25 -> Result: -1
  3. arr = [5, 1, 9, 3], target = 1 -> Result: 1

Conclusion

Today we solved the problem of finding a desired integer using C++. We learned how to find a specific number in an array using linear search. Such problems are often asked in real interviews, so you should practice enough to become proficient. In the next lesson, we will cover other algorithms and more complex problems, so stay tuned!

References

For more information, please refer to the following materials: