สมมติว่ามีอาร์เรย์และมีการจัดเรียง ให้พิจารณาว่าอาร์เรย์ถูกหมุนที่จุดหมุนบางจุด ซึ่งเราไม่รู้จัก ดังนั้นเราจึงต้องหาค่าต่ำสุดจากอาร์เรย์ที่หมุนนั้น ดังนั้นหากอาร์เรย์เป็นแบบ [3,4,5,1,2] ผลลัพธ์จะเป็น 1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ต่ำ :=0 และสูง :=ดัชนีสุดท้ายของอาร์เรย์ n :=ขนาดของอาร์เรย์ ans :=อินฟินิตี้
- ในขณะที่ต่ำ <=สูง
- กลาง :=ต่ำ + (สูง - ต่ำ)/2
- ถ้า arr[ต่ำ]
- else if arr[high]> arr[mid] แล้ว ans :=maximum of ans and arr[mid], high :=mid – 1
- มิฉะนั้น ถ้าต่ำ =กลาง แล้ว ans :=ขั้นต่ำของ ans และ arr[low], ต่ำ :=กลาง + 1
- มิฉะนั้น ถ้าสูง =กลาง แล้ว ans :=ขั้นต่ำของ ans และ arr[สูง], สูง :=กลาง - 1
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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;
}
};
main(){
Solution ob;
vector<int> v = {15,35,85,96,5,6,8,12};
cout << ob.findMin(v);
} อินพุต
[15,35,85,96,5,6,8,12]
ผลลัพธ์
5
