ตั้งพื้นใน Sorted Array ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ที่เรียงลำดับ arr[] และค่าจำนวนเต็ม x งานของเราคือสร้างโปรแกรมเพื่อค้นหา floor in a sorted array .

ชั้น X ในอาร์เรย์ที่จัดเรียง เป็นองค์ประกอบที่ใหญ่ที่สุดของอาร์เรย์ arr[] ซึ่งน้อยกว่าหรือเท่ากับ x

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

Input: arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10
Output: 9

คำอธิบาย − ในอาร์เรย์ 9 ข้างต้นเป็นจำนวนที่มากที่สุดซึ่งน้อยกว่าหรือเท่ากับ 10

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือโดยตรงโดยการสำรวจอาร์เรย์และค้นหาองค์ประกอบที่ตรงตามเงื่อนไข ขณะสำรวจอาร์เรย์

เราจะตรวจสอบแต่ละองค์ประกอบ ถ้ามันมากกว่า x ให้คืนค่าองค์ประกอบก่อนหน้าเป็นพื้นของ x

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <iostream>
using namespace std;

int findFloorSortedArray(int arr[], int n, int x){
   if (x >= arr[n - 1])
      return (n-1);
   if (x < arr[0])
      return -1;
   for (int i = 1; i < n; i++)
      if (arr[i] > x)
         return (i - 1);
   return -1;
}
int main(){
   int arr[] = {2, 5, 6, 8, 9, 12, 21, 25};
   int n = sizeof(arr) / sizeof(arr[0]);
   int x = 10;
   int floorIndex = findFloorSortedArray(arr, n - 1, x);
   if (floorIndex == -1)
      cout<<"The floor of "<<x<<" doesn't exist in the array";
   else
      cout<<"The floor of "<<x<<" in the array is "<<arr[floorIndex];
   return 0;
}

ผลลัพธ์

The floor of 10 in the array is 9

วิธีอื่น

วิธีอื่นในการแก้ปัญหาคือการใช้ อัลกอริทึมการค้นหาแบบไบนารี เนื่องจากอาร์เรย์ถูกจัดเรียงและงานของเราขึ้นอยู่กับการค้นหาค่า ในโซลูชันนี้ เราจะค้นหาองค์ประกอบที่อยู่ตรงกลางดัชนีของอาร์เรย์ จากนั้นตามองค์ประกอบตรงกลาง เราจะทำการค้นหาตัวเลขในครึ่งแรก (ครึ่งที่เล็กกว่า) หรือครึ่งหลัง (ครึ่งที่มากกว่า) ของอาร์เรย์เพิ่มเติม และทำต่อไปจนกว่าอาร์เรย์ทั้งหมดจะผ่านหรือพบองค์ประกอบที่ตรงกลางของอาร์เรย์ย่อย

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <iostream>
using namespace std;

int findFloorSortedArray(int arr[], int start, int end, int x){
   if (start > end)
      return -1;
   if (x >= arr[end])
      return end;
   int mid = (start + end) / 2;
   if (arr[mid] == x)
      return mid;
   if (mid > 0 && arr[mid - 1] <= x && x < arr[mid])
      return mid - 1;
   if (x < arr[mid])
      return findFloorSortedArray(arr, start, mid - 1, x);
   return findFloorSortedArray(arr, mid + 1, end, x);
}
int main(){
   int arr[] = {2, 5, 6, 8, 9, 12, 21, 25};
   int n = sizeof(arr) / sizeof(arr[0]);
   int x = 10;
   int floorIndex = findFloorSortedArray(arr, 0, n - 1, x);
   if (floorIndex == -1)
      cout<<"The floor of "<<x<<" doesn't exist in the array";
   else
      cout<<"The floor of "<<x<<" in the array is "<<arr[floorIndex];
   return 0;
}

ผลลัพธ์

The floor of 10 in the array is 9