Giả sử có một mảng đã được sắp xếp, nhưng mảng này bị xoay tại một điểm pivot không biết trước. Chúng ta phải tìm giá trị nhỏ nhất từ mảng đã xoay đó. Ví dụ, nếu mảng là [3,4,5,1,2], thì kết quả sẽ là 1.
Để giải quyết, chúng ta thực hiện các bước sau:
- low := 0 và high := chỉ số cuối cùng của mảng, n := kích thước mảng, ans := vô cực
- while low <= high
- mid := low + (high - low)/2
- if arr[low] < arr[mid], thì ans := min(ans, arr[low]), low := mid + 1
- else if arr[high] > arr[mid], thì ans := min(ans, arr[mid]), high := mid – 1
- else if low = mid, thì ans := min(ans, arr[low]), low := mid + 1
- else if high = mid, thì ans := min(ans, arr[high]), high := mid - 1
- return ans
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#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); }Input
[15,35,85,96,5,6,8,12]
Output
5