สมมติว่าเรามีหนึ่งอาร์เรย์ ซึ่งในตอนแรกเพิ่มขึ้นแล้วลดลง เราต้องหาค่าสูงสุดในอาร์เรย์ ดังนั้นหากองค์ประกอบอาร์เรย์เป็นเหมือน A =[8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1] ผลลัพธ์จะเป็น 500
เราสามารถใช้การค้นหาแบบไบนารีเพื่อแก้ปัญหานี้ได้ มีสามเงื่อนไข -
- เมื่อค่ากลางมีค่ามากกว่าองค์ประกอบที่อยู่ติดกันทั้งสอง ค่ากลางจะเป็นค่าสูงสุด
- หาก mid มากกว่าองค์ประกอบถัดไป แต่น้อยกว่าองค์ประกอบก่อนหน้า ค่า max จะอยู่ที่ด้านซ้ายของ mid
- หากองค์ประกอบกลางมีขนาดเล็กกว่าองค์ประกอบถัดไป แต่มากกว่าองค์ประกอบก่อนหน้า ค่าสูงสุดจะอยู่ทางด้านขวาขององค์ประกอบกลาง
ตัวอย่าง
#include<iostream>
using namespace std;
int getMaxElement(int array[], int left, int right) {
if (left == right)
return array[left];
if ((right == left + 1) && array[left] >= array[right])
return array[left];
if ((right == left + 1) && array[left] < array[right])
return array[right];
int mid = (left + right)/2;
if ( array[mid] > array[mid + 1] && array[mid] > array[mid - 1])
return array[mid];
if (array[mid] > array[mid + 1] && array[mid] < array[mid - 1])
return getMaxElement(array, left, mid-1);
else
return getMaxElement(array, mid + 1, right);
}
int main() {
int array[] = {8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1};
int n = sizeof(array)/sizeof(array[0]);
cout << "The maximum element is: " << getMaxElement(array, 0, n-1);
} ผลลัพธ์
The maximum element is: 450
