ในปัญหานี้ เราได้รับอาร์เรย์ที่จัดเรียงแล้ว arr[] และค่าจำนวนเต็ม x ภารกิจของเราคือการสร้างโปรแกรมหา floor ในอาร์เรย์ที่จัดเรียงแล้ว
Floor ของ X ในอาร์เรย์ที่จัดเรียงแล้ว arr คือองค์ประกอบที่ใหญ่ที่สุดของอาร์เรย์ arr[] ซึ่งน้อยกว่าหรือเท่ากับ x
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input: arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10 Output: 9
คำอธิบาย - ในอาร์เรย์ด้านบน 9 คือตัวเลขที่ใหญ่ที่สุดซึ่งน้อยกว่าหรือเท่ากับ 10
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการเดินทางผ่านอาร์เรย์โดยตรงและหาองค์ประกอบที่ตรงตามเงื่อนไข ขณะเดินทางผ่านอาร์เรย์
เราจะตรวจสอบแต่ละองค์ประกอบ หากมันมากกว่า x ให้คืนค่าองค์ประกอบก่อนหน้าเป็น floor ของ 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
วิธีการสลับ
วิธีสลับในการแก้ปัญหาคือการใช้ binary searching algorithm เนื่องจากอาร์เรย์จัดเรียงแล้วและภารกิจของเราเกี่ยวกับการหาค่า ในวิธีนี้ เราจะค้นหาองค์ประกอบที่ดัชนีกลางของอาร์เรย์ จากนั้นตามองค์ประกอบกลาง เราจะค้นหาตัวเลขในครึ่งแรก (ครึ่งที่น้อยกว่า) หรือครึ่งหลัง (ครึ่งที่มากกว่า) ของอาร์เรย์ และดำเนินต่อไปจนกว่าจะเดินทางผ่านอาร์เรย์ทั้งหมดหรือพบองค์ประกอบที่ตรงกลางของ sub-array
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#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
