Menu
I'm having a hard time solving this problem.
A[1..n] is an array of real numbers which is partially sorted:
There are some p,q (1 <= p <= q <=n) so:
A[1] <= ... <= A[p]
A[p] >= ... >= A[q]
A[q] <= ... <= A[n]
How can we find a value in this array in O(lgn)?
(You can assume that the value exists in the array)
793
An array is partially sorted if the number of inversions is less or equal a constant times the array length. if array length is N then (number of inversions) <= c*N, with c constant.
The main reason why binary search (which requires sorted data in a data structure with O(1) random access reads) is O(log N) is that for any given data set, we start by looking at the middle-most element.
If we know nothing about the distribution of key values, then we have just proved that binary search is the best algorithm available for searching a sorted array.
The idea is to find the pivot point, divide the array into two sub-arrays and perform a binary search. For a sorted (in increasing order) and rotated array, the pivot element is the only element for which the next element to it is smaller than it. Using binary search based on the above idea, pivot can be found.
Make 3 binary searches: from 1 to p, p to q and q to n. The complexity is still O(logn).
Since we don't know p and q:
You cannot solve this problem in logn time. Assume a case where you have a sorted list of positive numbers with one zero mixed in (p+1=q and A[q]=0). This situation satisfies all the criteria you mentioned. Now, the problem of finding where that zero is located cannot be solved in sub O(n) time. Therefore your problem cannot be solved in O(logn) time.
122
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
