Normally binary search works only on fully sorted arrays, but here one half is always sorted, and that is the key logic.
Main Idea
At every step:
- Find mid
- Check which half is sorted
- Decide whether target lies inside that sorted half
- Move accordingly
why this approach?
In a rotated sorted array:
- At least one half is always sorted.
- Using that sorted half, we can decide where target can exist.
- So every iteration removes half the array.
complexity:
Time: O(log n)
Space: O(1)
CODE
class Solution {
public int search(int[] a, int t) {
int low = 0, high = a.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] == t) {
return mid;
}
if (a[low] <= a[mid]) {
if (a[low] <= t && t <= a[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
} else {
if (a[mid] <= t && t <= a[high]) {
low=mid+1;
}else{
high=mid-1;
}
}
}
return -1;
}
}
Vollständiger Original-Bericht
Ausführliche Details, Code-Beispiele & Hersteller-Stellungnahme auf dev.to.
SOCIAL SHARE CARD GENERATOR