I'm trying to find minimum in array which has this kind of structure in general:
Array consists of non-negative integers [0; 1e5-1]. It may contain any number of such steps, be sorted or just a constant. I want to find it in O(logn) thats why I'm using binary search. This code handle all cases except cases there is any plateau:
size_t left = 0, right = arr.size() - 1;
while (left < right) {
const size_t mid = left (right - left) / 2;
if ((mid == 0 || arr[mid] < arr[mid - 1]) && (mid 1 == size || arr[mid] < arr[mid 1])) {
return mid;
}
if (arr[mid] > arr[mid 1] || arr[mid] > arr[right]) {
left = mid 1;
}
else {
right = mid;
}
}
return left;
Example of bad input: [4, 3, 3, 2, 1, 2].
Unfortenatly, I'm out of ideas how to fix this cases. Maybe it's even impossible. Thank you in advance.
CodePudding user response:
I am afraid it is not possible to do in log n
time in general.
- Assume an array of
n
elements equal to1
and a single element of0
. - Your problem now reduces into finding that
0
element. - By "visiting" (=indexing) any member
1
you gain no knowledge about position of0
- making the search order irrelevant. - Therefore you have to visit every element to find where the
0
is.
If you really want, I think the following algorithm should be roughly O(log n #elements-on-plateaus)
- Set
left, right
as for binary search - Compute
middle
. - Go left from
middle
until:- If you find a decrease, set
right=pos
wherepos
is the decreased element and go 4. - If you find an increase, set
left=pos
wherepos
is the increased element and go 4. - If you reach
left
position, go right frommiddle
instead and do the analogous actions.- [X] If you reach
right
too, you are on a plateau and range[left,right]
are the minimal elements of the array.
- [X] If you reach
- If you find a decrease, set
- Repeat until you hit [X].