สมมติว่าเราได้รับอาเรย์ 'arr' ที่มี n จำนวนเต็มเรียงลำดับแล้ว และอาเรย์ 'query' ขนาด q เราต้องบอกว่าแต่ละค่าใน query มีอยู่ใน arr หรือไม่ ถ้ามีพิมพ์ "Present" พร้อมตำแหน่ง (1-indexed) ถ้าไม่มีพิมพ์ "Not present" พร้อมตำแหน่งของค่าน้อยที่สุดที่มากกว่าค่าใน query
เช่น n = 8, arr = {1, 2, 3, 4, 7, 9, 12, 15}, q = 3, query = {1, 5, 8} ผลลัพธ์:
Present 1 Not present 5 Not present 6
ค่า 1 อยู่ตำแหน่ง 1, ค่า 5 ไม่มี ค่าน้อยที่สุดมากกว่า 5 คือ 7 อยู่ตำแหน่ง 5, ค่า 8 ไม่มี ค่าน้อยที่สุดมากกว่า 8 คือ 9 อยู่ตำแหน่ง 6
ขั้นตอนการแก้ปัญหา
- เก็บค่า arr ลงใน vector values
- วนลูปทุก query[i]:
- idx := lower_bound(values, query[i]) - values.begin()
- ถ้า values[idx] == query[i] พิมพ์ "Present "
- มิฉะนั้นพิมพ์ "Not present "
- พิมพ์ idx + 1 (เพราะ 1-indexed)
ตัวอย่างโค้ด
#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; }
อินพุต
int input_arr[] = {1, 2, 3, 4, 7, 9, 12, 15}; int query_arr[] = {1, 5, 8}; solve(8, input_arr, 3, query_arr);
เอาต์พุต
Present 1 Not present 5 Not present 6
