ในปัญหานี้ เราได้รับอาร์เรย์ที่ประกอบด้วยตัวเลขที่เรียงลำดับและมีขนาดอนันต์ งานของเราคือ หาตำแหน่งขององค์ประกอบในอาร์เรย์เรียงลำดับขนาดอนันต์
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input
arr[] = {2, 4, 6, 8, 9, 12, 14, 17, ...}, ele = 9
Output
4
อธิบาย
วิธีแก้ปัญหา
สำหรับการค้นหาองค์ประกอบจากอาร์เรย์เรียงลำดับอย่างมีประสิทธิภาพ เราจะใช้ binary search แต่เนื่องจากไม่รู้จุดสิ้นสุด เราจะปรับอัลกอริทึมเล็กน้อย
เราจะกำหนด start pointer ที่ตำแหน่งแรก แล้วตั้ง end pointer ที่ตำแหน่งที่สอง หลังจากนั้น ตรวจสอบค่าที่ end pointer และเพิ่มค่าเป็นสองเท่าถ้าค่าน้อยกว่าคีย์ และอัปเดต start pointer ด้วยตำแหน่งล่าสุดของ end pointer
เมื่อค่าตำแหน่งสุดท้ายมากกว่าองค์ประกอบที่ต้องการ เราจะค้นหาใน subarray นี้โดยใช้ binary search
โปรแกรมแสดงการทำงานของวิธีแก้
ตัวอย่าง
#include<iostream>
using namespace std;
int binarySearch(int arr[], int start, int end, int ele) {
if (end >= start) {
int mid = start + (end - start)/2;
if (arr[mid] == ele)
return mid;
if (arr[mid] > ele)
return binarySearch(arr, start, mid-1, ele);
return binarySearch(arr, mid+1, end, ele);
}
return -1;
}
int findPos(int arr[], int value) {
int start = 0, end = 1;
while (arr[end] < value) {
start = end;
end = 2*end;
}
return binarySearch(arr, start, end, value);
}
int main(){
int arr[] = {1, 2, 4, 6, 8, 9, 12, 14, 17, 21, 45};
int index = findPos(arr, 9);
if (index == -1)
cout<<"Element not found!";
else
cout<<"Element found! index = "<<index;
return 0;
}
ผลลัพธ์
Element found! index = 5
