การนับองค์ประกอบที่เล็กกว่าหรือเท่ากันในอาร์เรย์ที่จัดเรียงใน 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) คืนค่าจำนวนขององค์ประกอบของ arr[] ที่เล็กหรือเท่ากับ K

• ใช้ตัวแปรเริ่มต้นนับเป็น 0 สำหรับตัวเลขดังกล่าว

• อาร์เรย์การเคลื่อนที่ของตัวเลขโดยใช้ for loop 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) คืนค่าจำนวนขององค์ประกอบของ arr[] ที่เล็กหรือเท่ากับ K

• ใช้ดัชนีต่ำ=0,สูง=len-1และกลาง=(ต่ำ+สูง)/2;/p>

• ใช้ดัชนีตัวแปร=-1;

• ใช้ while loop จนถึงระดับต่ำ<=high

• ตรวจสอบค่าของ arr[mid] ถ้าเป็น <=k จากนั้น index=mid ใหม่ ต่ำ=กลาง+1

• มิฉะนั้น new high=mid-1.

• ที่ส่วนท้ายของ while loop index จะเป็นดัชนีของตัวเลขสุดท้าย<=k.

• ส่งคืน index+1 เป็นผลลัพธ์เนื่องจากการจัดทำดัชนีอาร์เรย์เริ่มต้นจาก 0 และตัวเลขทั้งหมดจากดัชนี 0 ถึงดัชนีมีค่าน้อยกว่า k

ตัวอย่าง

#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