ในปัญหานี้ เราได้รับอาร์เรย์ที่ประกอบด้วยตัวเลขที่เรียงเป็นอนันต์ หน้าที่ของเราคือค้นหาตำแหน่งขององค์ประกอบในอาร์เรย์ที่เรียงลำดับของจำนวนอนันต์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {2, 4, 6, 8, 9, 12, 14,17, ….}, ele = 9 ผลลัพธ์
4
คำอธิบาย
แนวทางการแก้ปัญหา
สำหรับการค้นหาองค์ประกอบจากอาร์เรย์ที่จัดเรียงอย่างมีประสิทธิภาพ เราจะใช้วิธีการค้นหาแบบไบนารี ที่นี่ ไม่ทราบจุดสิ้นสุดเพียงจุดเดียว เราจะปรับเปลี่ยนอัลกอริทึมเล็กน้อย
เราจะแก้ไขตัวชี้เริ่มต้นไปที่ตำแหน่งแรก จากนั้นนำตัวชี้สิ้นสุดไปที่ตำแหน่งที่สอง หลังจากนี้ เราจะตรวจสอบค่าที่จุดสิ้นสุดและเพิ่มขึ้นโดยเพิ่มเป็นสองเท่าหากค่าน้อยกว่าคีย์ และอัปเดตตัวชี้จุดเริ่มต้นด้วยตำแหน่งสุดท้ายของตัวชี้จุดสิ้นสุด
เมื่อค่าตำแหน่งสุดท้ายมากกว่าองค์ประกอบที่จะพบ เราจะค้นหาในอาร์เรย์ย่อยนี้โดยใช้การค้นหาแบบไบนารี
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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
