สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n เราต้องหาค่าขั้นต่ำท้องถิ่นของอาร์เรย์ ในอาร์เรย์ A องค์ประกอบ A[x] ถูกกล่าวถึงว่าเป็นค่าต่ำสุดในพื้นที่ หากมีค่าน้อยกว่าหรือเท่ากับเพื่อนบ้านทั้งสอง สำหรับองค์ประกอบมุมจะพิจารณาเพื่อนบ้านเพียงคนเดียว และหากมีค่าขั้นต่ำในเครื่องมากกว่าหนึ่งรายการ ให้ส่งคืนเพียงรายการเดียว ตัวอย่างเช่น หากอาร์เรย์เป็นแบบ [9, 6, 3, 14, 5, 7, 4] ค่าต่ำสุดในเครื่องอาจเป็น 3, 5 และ 4 ดังนั้นอัลกอริธึมนี้สามารถคืนค่าได้เพียงรายการเดียวเท่านั้น
เพื่อแก้ปัญหานี้ เราจะใช้ตรรกะเช่นการค้นหาไบนารี หากองค์ประกอบกลางมีค่าน้อยกว่าองค์ประกอบด้านซ้ายและขวา ให้คืนค่ากลาง มิฉะนั้น หากองค์ประกอบตรงกลางมีค่าน้อยกว่าองค์ประกอบด้านซ้าย อาจมีค่าต่ำสุดที่ด้านซ้ายมือ หากมีค่ามากกว่าองค์ประกอบด้านขวา จะเป็นค่าต่ำสุดในพื้นที่ทางด้านขวา ทำงานแบบเดียวกันเพื่อค้นหาค่าต่ำสุดในพื้นที่ที่แน่นอน
ตัวอย่าง
#include<iostream>
using namespace std;
int localMinima(int arr[], int left, int right, int n) {
int mid = left + (right - left)/2;
if ((mid == 0 || arr[mid-1] > arr[mid]) && (mid == n-1 || arr[mid+1] > arr[mid]))
return mid;
else if (mid > 0 && arr[mid-1] < arr[mid])
return localMinima(arr, left, (mid -1), n);
return localMinima(arr, (mid + 1), right, n);
}
int findLocalMinima(int arr[], int n) {
return localMinima(arr, 0, n-1, n);
}
int main() {
int arr[] = {9, 6, 3, 14, 5, 7, 4};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Local minima is: " << arr[findLocalMinima(arr, n)];
} ผลลัพธ์
Local minima is: 3
