ภาพรวมปัญหา
มีอาร์เรย์ที่จัดเรียงแล้ว แต่ถูกหมุน (rotate) ที่จุด pivot ไหนไม่ทราบ ต้องหาค่าต่ำสุดจากอาร์เรย์ที่หมุนแล้ว
ตัวอย่าง: [3,4,5,1,2] → ค่าต่ำสุดคือ 1
อัลกอริทึม (Binary Search)
- low := 0, high := ดัชนีสุดท้าย, ans := infinity
- while low ≤ high:
- mid := low + (high - low)/2
- ถ้า arr[low] < arr[mid] → ans = min(ans, arr[low]), low = mid + 1
- ถ้า arr[high] > arr[mid] → ans = min(ans, arr[mid]), high = mid - 1
- ถ้า low = mid → ans = min(ans, arr[low]), low = mid + 1
- ถ้า high = mid → ans = min(ans, arr[high]), high = mid - 1
- return ans
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMin(vector<int>& arr) {
int low = 0;
int high = arr.size() - 1;
int n = arr.size();
int ans = INT_MAX;
while(low <= high){
int mid = low + (high - low) / 2;
if(arr[low] < arr[mid]){
ans = min(ans, arr[low]);
low = mid + 1;
} else if(arr[high] > arr[mid]) {
ans = min(ans, arr[mid]);
high = mid - 1;
} else if(low == mid) {
ans = min(ans, arr[low]);
low = mid + 1;
} else if(high == mid) {
ans = min(ans, arr[high]);
high = mid - 1;
}
}
return ans;
}
};
int main(){
Solution ob;
vector<int> v = {15,35,85,96,5,6,8,12};
cout << ob.findMin(v);
}
Input / Output
Input: [15,35,85,96,5,6,8,12] Output: 5
