0
$\begingroup$

So, there's a LeetCode problem that has you find a O(log n) solution to finding a target number in a rotated sorted array.

As an example:

array = [5,6,7,1,2,3]
target = 4

Basically, the trick is that you can find the point of rotation in O(log n) time and then you can do a binary search over the appropriate subsection in O(log n) time to find the index of the target (if it exists) in the array.

This sort of got me thinking, what are the conditions under which you can do a O(log n) search for an element in an array in which all numbers are distinct?

Clearly, you can still do a O(log n) search even if the array is something less than strictly sorted. But, I don't know how far you can push the array before it is no longer searchable in log n time.

How would one look to solve or describe a problem like this?

$\endgroup$
1
  • $\begingroup$ The rotated array is "$O(\log n)$ away" from being sorted. This condition is necessary. $\endgroup$
    – user16034
    Commented May 18, 2022 at 8:50

2 Answers 2

1
$\begingroup$

I think you essentially answered it yourself (and @Yves Daoust) with the point that there's an O(log(n)) trick.

We could say that it's the set of problems for which you can modify a known O(log(n)) algorithm by adding O(log(n)) operations.

You asked for "the conditions" under which an array can be searched in O(log(n)). The answer above is informal, but I expect there's a nice mathematical way to express it. That might start with defining a problem as a set of arrays, such as a set identified by some conditions or specification; e.g., "any array that is a rotation of a sorted array."

In the case of the rotated array, the added operations are finding the smallest or largest element, which can be done in O(log(n)).

Another example: if you have an array of numbers such that every number is no more than 10 positions away from where it would be if sorted, then you modify a binary search algorithm by walking the 20 positions surrounding the point where the algorithm expected to find it. That's just adding a constant number of operations (~20), which is less than O(log(n)).

I think we could keep coming up with new O(log(n)) problems by taking one of these that we've discovered and "perverting" it. For example, we could have a rotated array with numbers no more than 10 spots away from their rotated-sorted position. That sounds a little more complicated, but I expect it's still O(log(n)).

I believe the ways the problem could be modified are infinite and potentially very complicated, so it's probably not worth trying to identify them . . . unless you are looking for good job interview questions.

$\endgroup$
4
  • $\begingroup$ Note that it's not just the set of problems where the input is modified by O(log(n)) operations. Rotating an array sounds like a linear (O(n)) transformation which is bigger than O(log(n)). $\endgroup$
    – bjc
    Commented Jan 13, 2023 at 4:35
  • $\begingroup$ The rotation is canceled implicitly, by modifying the indexing scheme. No element is moved. In fact, this operation has no cost in the asymptotic sense. $\endgroup$
    – user16034
    Commented Jan 13, 2023 at 8:50
  • $\begingroup$ @YvesDaoust, if you need to find the start and end before modifying the indexing, that can cost log(n). $\endgroup$
    – bjc
    Commented Jan 17, 2023 at 22:43
  • $\begingroup$ @YvesDaoust, if you're commenting on my comment about modifying the input being linear, I was assuming that the input would be a string or an array in which case modifying that string input would be O(n). I think modifying the indices would be modifying the algorithm, not the input. $\endgroup$
    – bjc
    Commented Jan 17, 2023 at 22:53
0
$\begingroup$

I would begin by considering the time complexity of an array in absolute worst or best case before concerning with any slight deviations from average. I don't know if you are going to get discernable results.

$\endgroup$
1
  • $\begingroup$ I am not sure that this is of any help. $\endgroup$
    – user16034
    Commented May 18, 2022 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.