C++에서 정렬된 배열의 더 작거나 같은 요소 수

<시간/>

정수 배열이 제공됩니다. 목표는 주어진 값 K보다 작거나 같은 배열 요소의 개수를 찾는 것입니다.

입력

Arr[]= { 1, 2, 3, 14, 50, 69, 90 } K=12

출력

Numbers smaller or equal to K: 3

설명

Numbers 1,2,3 is smaller or equal to 12.

입력

Arr[]= { 12, 13, 13, 13, 14, 50, 54, 100 } K=14

출력

Numbers smaller or equal to K: 5

설명

Numbers 12, 13, 14 are smaller or equal to 14.

순진한 접근

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

정수 배열 Arr[] 및 K를 사용합니다.
smallorEqual(int arr[],int k,int len) 함수는 K
보다 작거나 같은 arr[] 요소의 개수를 반환합니다.
이러한 숫자에 대해 초기 변수 개수를 0으로 간주합니다.
for 루프를 사용하여 숫자 배열을 탐색합니다. i=0 ~ i
이제 각 숫자 arr[i]에 대해 <=k이면 카운트를 증가시킵니다.
마지막 루프 카운트에는 조건을 만족하는 총 수가 있습니다.
카운트를 결과로 반환합니다.

예시

#include <bits/stdc++.h>
using namespace std;
int smallorEqual(int arr[],int k,int len){
   int count = 0;
   for (int i = 0; i < len; i++){
      if(arr[i]<=k)
         { count++; }
      else
         { break; }
   }
   return count;
}
int main(){
   int Arr[] = { 1,5,11,12,19,21,32,53,70,100 };
   int K = 21;
   int Length= sizeof(Arr)/sizeof(Arr[0]);
   cout <<"Numbers smaller or equal to K: "<<smallorEqual(Arr,K,Length);
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -

Numbers smaller or equal to K: 6

효율적인 접근 방식(바이너리 검색 사용)

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

정수 배열 Arr[] 및 K를 사용합니다.
함수 binarySearch(int arr[],int k,int len)는 K
보다 작거나 같은 arr[] 요소의 개수를 반환합니다.
인덱스를 low=0, high=len-1 및 mid=(low+high)/2로 가져옵니다./p>
변수 인덱스=-1 가져오기;
while 루프를 사용하여 low<=high
까지
arr[mid]의 값을 확인하십시오. <=k인 경우. 그런 다음 인덱스 =중간입니다. 새로운 낮은=중간+1
그렇지 않으면 새로운 high=mid-1.
while 루프 인덱스가 끝나면 마지막 숫자<=k의 인덱스가 됩니다.
배열 인덱싱은 0부터 시작하고 인덱스 0부터 인덱스까지의 모든 숫자가 k보다 작기 때문에 index+1을 결과로 반환합니다.

예시

#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[],int k,int len){
   int low = 0;
   int high = len -1;
   int mid = (high+low)/2;
   int index = -1;
   while(low <= high){
      mid =( low + high ) / 2;
      if(arr[mid] <= k){
         index = mid;
         low = mid+1;
      }
      else{
         high=mid-1;
      }
   }
   return (index+1);
}
int main(){
   int Arr[] = { 1,5,11,12,19,21,32,53,70,100 };
   int K = 21;
   int Length= sizeof(Arr)/sizeof(Arr[0]);
   cout <<"Numbers smaller or equal to K: "<<binarySearch(Arr,K,Length);
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -

Numbers smaller or equal to K: 6