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