배열의 특정 값을 검색하는 C++ 프로그램

<시간/>

n개의 정렬된 정수 값을 포함하는 배열 'arr'이 있다고 가정합니다. 우리는 또한 크기 q의 배열 'query'를 받았고, 'query'의 값이 주어진 배열 'arr'에 존재하는지 여부를 알려야 합니다. 쿼리의 값이 arr에 있으면 값이 위치한 위치와 함께 "Present"를 인쇄합니다. 그렇지 않으면 "Not present"를 인쇄하고 Arr에 위치를 인쇄합니다. 여기서 최소값은 의 값보다 큽니다. 쿼리가 위치합니다. 배열이 1-인덱싱된다는 것을 기억해야 합니다.

따라서 입력이 n =8, arr ={1, 2, 3, 4, 7, 9, 12, 15} , q =3, 쿼리 ={1, 5, 8}인 경우 출력은 다음과 같습니다.

Present 1
Not present 5
Not present 6

쿼리의 첫 번째 값은 arr의 1번 위치에 있습니다.

쿼리의 두 번째 값은 arr에 없습니다. 쿼리에서 값보다 큰 최소값이 5인 위치입니다.

마찬가지로 쿼리의 세 번째 값도 arr에 없습니다. arr의 6번 위치에 있는 값보다 큰 값입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

배열 값 정의
초기화 i의 경우:=0, i
값 끝에 arr[i] 삽입

i를 초기화하기 위해:=0, i

idx :=(query[i]보다 작지 않은 값의 첫 번째 요소 위치) - 값의 첫 번째 요소 위치

값[idx]이 쿼리[i]와 같으면 -

print("현재 ")

그렇지 않으면,

print("존재하지 않음")

인쇄(idx + 1)

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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