คำอธิบาย
กำหนดอาร์เรย์ที่เรียงลำดับแล้วขององค์ประกอบที่ไม่ซ้ำกัน ซึ่งถูกหมุน (rotated) ที่จุดที่ไม่ทราบ งานคือการหาค่าสูงสุดในอาร์เรย์
ตัวอย่าง
ถ้าอาร์เรย์นำเข้าคือ {30, 40, 50, 10, 20} ค่าสูงสุดคือ 50
อัลกอริทึม
- ค่าสูงสุดคือองค์ประกอบเพียงตัวเดียวที่องค์ประกอบถัดไปของมันมีค่าน้อยกว่า ถ้าไม่มีองค์ประกอบถัดไปที่น้อยกว่า แสดงว่าไม่มีการหมุน นั่นคือองค์ประกอบสุดท้ายคือค่าสูงสุด
- เราตรวจสอบเงื่อนไขนี้สำหรับองค์ประกอบกลาง (middle element) โดยเปรียบเทียบกับองค์ประกอบที่ mid – 1 และ mid + 1 ถ้าค่าสูงสุดอยู่กับองค์ประกอบที่ mid – 1 และ mid + 1 ถ้าค่าสูงสุดไม่อยู่ตรงกลาง (ไม่ใช่ mid และไม่ใช่ mid + 1) แล้ว ค่าสูงสุดจะอยู่ในครึ่งซ้ายหรือครึ่งขวา:
- ถ้าองค์ประกอบกลางมากกว่าองค์ประกอบสุดท้าย ค่าสูงสุดจะอยู่ในครึ่งซ้าย
- มิฉะนั้น ค่าสูงสุดจะอยู่ในครึ่งขวา
ตัวอย่างโค้ด
#include <bits/stdc++.h> using namespace std; int getMaxinSortedAndRorated(int *arr, int low, int high) { if (high < low) { return arr[0]; } if (high == low) { return arr[high]; } int mid = low + (high - low) / 2; if (mid < high && arr[mid + 1] < arr[mid]) { return arr[mid]; } if (mid > low && arr[mid] < arr[mid - 1]) { return arr[mid - 1]; } if (arr[low] > arr[mid]) { return getMaxinSortedAndRorated(arr, low, mid - 1); } else { return getMaxinSortedAndRorated(arr, mid + 1, high); } } int main() { int arr[] = {30, 40, 50, 10, 20}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Maximum element = " << getMaxinSortedAndRorated(arr, 0, n - 1) << endl; return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้:
Maximum element = 50
