สมมติว่ามีอาร์เรย์ที่เรียงลำดับแล้ว แต่ถูกหมุน (rotate) ที่จุดพิвотที่ไม่ทราบ เราต้องหาค่าสูงสุดจากอาร์เรย์ที่ถูกหมุนแล้ว
เช่น อาร์เรย์ [3,4,5,1,2] ค่าสูงสุดคือ 5
ขั้นตอนการแก้ปัญหา
- ใช้ Binary Search แบบปรับเปลี่ยน (Modified Binary Search)
- low = 0, high = n-1
- วนลูป while low <= high:
- mid = low + (high - low) / 2
- ถ้า arr[low] < arr[mid]: ค่าสูงสุดอยู่ขวา mid, อัปเดต ans และ low = mid + 1
- ถ้า arr[high] > arr[mid]: ค่าสูงสุดอยู่ซ้าย mid, อัปเดต ans และ high = mid - 1
- กรณีขอบ: low == mid หรือ high == mid จัดการแยก
- คืนค่า ans
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int search(vector<int>& arr, int low, int high) {
if (low == high) return arr[low];
int mid = low + (high - low) / 2;
int ans = 0;
if (arr[low] < arr[mid]) {
ans = max(arr[low], search(arr, mid, high));
} else if (arr[high] > arr[mid]) {
ans = max(arr[mid], search(arr, low, mid));
} else if (arr[low] == arr[mid]) {
ans = max(arr[low], search(arr, low + 1, high));
} else if (arr[high] == arr[mid]) {
ans = max(arr[high], search(arr, low, high - 1));
}
return ans;
}
int findMax(vector<int>& nums) {
return search(nums, 0, nums.size() - 1);
}
};
int main() {
Solution ob;
vector<int> v = {4, 5, 5, 5, 6, 8, 2, 3, 4};
cout << (ob.findMax(v));
}
อินพุต
[4,5,5,5,6,8,2,3,4]
เอาต์พุต
8
