patternMinor
Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))
Viewed 0 times
theelementslogwitharrayandpositionminthatelement
Problem
Given a sorted array $A[1,\ldots,n]$ and element $x$ that located at
position $k$. We know $x$, we don't know $k$. Write an algorithm that finds $k$, in $O(\min(\log k, \log(n-k))$ time complexity.
Any ideas how to solve this?
position $k$. We know $x$, we don't know $k$. Write an algorithm that finds $k$, in $O(\min(\log k, \log(n-k))$ time complexity.
Any ideas how to solve this?
Solution
Check the first element. Then check the last. Then the second, then the second to last, then the fourth, then the fourth to last, then the eighth, and so on. Stop upon bounding the location of x to a region at the front or back of the list.
Once you've bounded it you can just do a binary search.
Can you see why this works?
Once you've bounded it you can just do a binary search.
Can you see why this works?
Context
StackExchange Computer Science Q#104291, answer score: 4
Revisions (0)
No revisions yet.