{"id":34270,"date":"2024-11-01T09:26:14","date_gmt":"2024-11-01T09:26:14","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34270"},"modified":"2024-11-01T10:57:55","modified_gmt":"2024-11-01T10:57:55","slug":"c-coding-test-course-finding-desired-integer","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34270\/","title":{"rendered":"C++ Coding Test Course, Finding Desired Integer"},"content":{"rendered":"
\n

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.<\/p>\n\n

Problem Description<\/h2>\n

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

Input<\/h3>\n
arr = [2, 3, 4, 7, 11, 15, 20]\ntarget = 7\n<\/code><\/pre>\n
Output<\/h3>\n
Result: 3\n<\/code><\/pre>\n
Problem Analysis<\/h2>\n
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.<\/p>\n
Algorithm Choice<\/h2>\n
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).<\/p>\n
Linear Search Algorithm<\/h2>\n
The basic idea of linear search is as follows:<\/p>\n
    \n
  1. Start from the first element of the array.<\/li>\n
  2. Compare each element of the array sequentially until you find the desired integer.<\/li>\n
  3. If found, return the index of that element.<\/li>\n
  4. If not found by the end of the array, return -1<\/code>.<\/li>\n<\/ol>\n
    Code Implementation<\/h2>\n
    Now let\u2019s implement the linear search algorithm in C++. I have written the code below:<\/p>\n
    #include <iostream>\n#include <vector>\n\nint findTarget(const std::vector<int> &arr, int target) {\n    for (size_t i = 0; i < arr.size(); ++i) {\n        if (arr[i] == target) {\n            return i; \/\/ Target found, return index\n        }\n    }\n    return -1; \/\/ Target not found\n}\n\nint main() {\n    std::vector<int> arr = {2, 3, 4, 7, 11, 15, 20};\n    int target = 7;\n\n    int index = findTarget(arr, target);\n    if (index != -1) {\n        std::cout << \"Result: \" << index << std::endl;\n    } else {\n        std::cout << \"Result: -1\" << std::endl;\n    }\n\n    return 0;\n}<\/code><\/pre>\n
    Code Explanation<\/h2>\n
    In the above code, the findTarget<\/strong> function takes the array and the value to find as input and returns that value found in the array.<\/p>\n
      \n
    1. Access each element of the array through a for loop.<\/li>\n
    2. Check if the current element is equal to target<\/code>. If so, return the corresponding index.<\/li>\n
    3. If not found after checking all elements, return -1<\/code> to indicate ‘not found’.<\/li>\n<\/ol>\n
      Performance Analysis<\/h2>\n
      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).<\/p>\n
      Testing<\/h2>\n
      Now let\u2019s create some test cases to verify the validity of the algorithm.<\/p>\n
      Test Cases<\/h3>\n
        \n
      1. arr = [1, 2, 3, 4, 5]<\/code>, target = 3<\/code> -> Result: 2<\/code><\/li>\n
      2. arr = [10, 20, 30, 40, 50]<\/code>, target = 25<\/code> -> Result: -1<\/code><\/li>\n
      3. arr = [5, 1, 9, 3]<\/code>, target = 1<\/code> -> Result: 1<\/code><\/li>\n<\/ol>\n
        Conclusion<\/h2>\n
        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!<\/p>\n
        References<\/h2>\n
        For more information, please refer to the following materials:<\/p>\n