Chương trình C++ tìm kiếm giá trị cụ thể trong mảng

Giả sử chúng ta có mảng arr chứa n số nguyên đã sắp xếp. Cũng cho mảng query kích thước q. Với mỗi giá trị trong query, kiểm tra xem nó có trong arr hay không. Nếu có, in "Present" và vị trí (1-indexed). Nếu không, in "Not present" và vị trí của phần tử nhỏ nhất lớn hơn giá trị query.

Ví dụ: n = 8, arr = {1, 2, 3, 4, 7, 9, 12, 15}, q = 3, query = {1, 5, 8}. Kết quả: "Present 1 Not present 5 Not present 6".

Giải thuật

• Copy arr vào vector values
• Với mỗi query[i]: idx = lower_bound(values.begin(), values.end(), query[i]) - values.begin()
• Nếu values[idx] == query[i]: in "Present ", ngược lại in "Not present "
• In idx + 1 (vì 1-indexed)

Ví dụ minh họa

#include <vector> 
#include <iostream> 
using namespace std; 

void solve(int n, int arr[], int q, int query[]) { 
    vector<int> values; 
    for(int i = 0; i < n; i++){ 
        values.push_back(arr[i]); 
    } 
    for(int i = 0; i < q; i++) { 
        int idx = lower_bound(values.begin(), values.end(), query[i]) - values.begin(); 
        if (values[idx] == query[i]) 
            cout << "Present "; 
        else 
            cout << "Not present "; 
        cout << idx + 1 << endl; 
    } 
} 

int main() { 
    int input_arr[] = {1, 2, 3, 4, 7, 9, 12, 15}; 
    int query_arr[] = {1, 5, 8}; 
    solve(8, input_arr, 3, query_arr); 
    return 0; 
} 

Đầu vào

int input_arr[] = {1, 2, 3, 4, 7, 9, 12, 15}; int query_arr[] = {1, 5, 8}; solve(8, input_arr, 3, query_arr);

Đầu ra

Present 1 Not present 5 Not present 6