Search in Rotated Sorted Array in O(log n) time

Question

I have had a tough time with this problem on leetcode.

I've had to look up solutions because for some reason, my code would always end up having some issue. The current code I have, still loops infinitely when looking for a target number in the array that does not exist.

I am looking for some help on understanding if there is a more intuitive way to solve this problem and also help fixing my code.

I don't think I should need this line:

if nums[mid] == target or nums[low] == target or nums[high] == target:
            return target

And am wondering what I can do to make sure that if I have an array with 1-3 numbers, that my code can find the target without having to specify this conditional statement. Here are a couple examples

print(search([1, 2, 3], 1))
print(search([1], 1))
print(search([2, 1], 1))

Also, with an example like this print(search([5, 1, 2, 3, 4], 6)) my code never returns -1

def search(nums, target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target or nums[low] == target or nums[high] == target:
            return target
        if nums[mid] <= nums[high]:
            if target > nums[mid] and target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
        elif nums[mid] > nums[low]:
            if target >= nums[low] and target < nums[mid]:
                high = mid - 1
            else:
                low = mid+1
    return -1


print(search([1, 2, 3], 1))
print(search([5, 4, 1, 2, 3], 2))
print(search([3, 4, 5, 1, 2], 2))
print(search([1], 1))
print(search([2, 1], 1))
print(search([5, 1, 2, 3, 4], 6))

From coming across multiple solutions similar to the one I have above, people are saying it is O(logn) but I don't understand how when we are moving our low and high by 1. This makes me believe that the solution is worst case O(n)

Looking for some help!

Irby

Well one issue I see is that you are doing return target when you should be returning the index of target. – Chuck

You are not moving low and high by 1. You are moving it 1 point from the middle (since you have already tested that middle does not contain the correct value). Thus, in each step, you are cutting half of the search space, making it O(log n). – Cecrops

Answer 1

Here is a slightly different version

def search(nums, target):
    low = 0
    high = len(nums)-1

    while low <= high:

        mid = (low + high) // 2

        l = nums[low]
        m = nums[mid]
        h = nums[high]

        if target == l:
            return low

        if target == m:
            return mid

        if target == h:
            return high

        if any([
            l < m < h and target < m,
            l == m < h and target > m,
            l > m < h and target > l and target > m,
            l > m < h and target < l and target < m,
            l < m > h and target > l and target < m
        ]):
            high = mid

        elif any([
            l < m < h and target > m,
            l > m < h and target > m and target < h,
            l < m > h,
        ]):
            low = mid

        elif target < l or target > h:
            break

        elif l == m == h:
            break

        else:
            raise Exception("This is not possible, only if some values are reverse/unordered!")

    return -1

Tested with this data (first column is the target, the second is the list and the third column is the result index):

  -10 [1]                      -1
    1 [1]                       0
   22 [1]                      -1
  -10 [1, 2]                   -1
    1 [1, 2]                    0
    2 [1, 2]                    1
   22 [1, 2]                   -1
  -10 [2, 1]                   -1
    1 [2, 1]                    1
    2 [2, 1]                    0
   22 [2, 1]                   -1
  -10 [1, 5]                   -1
    1 [1, 5]                    0
    5 [1, 5]                    1
   22 [1, 5]                   -1
  -10 [5, 1]                   -1
    1 [5, 1]                    1
    5 [5, 1]                    0
   22 [5, 1]                   -1
  -10 [1, 2, 3]                -1
    1 [1, 2, 3]                 0
    2 [1, 2, 3]                 1
    3 [1, 2, 3]                 2
   22 [1, 2, 3]                -1
  -10 [3, 1, 2]                -1
    1 [3, 1, 2]                 1
    2 [3, 1, 2]                 2
    3 [3, 1, 2]                 0
   22 [3, 1, 2]                -1
  -10 [2, 3, 1]                -1
    1 [2, 3, 1]                 2
    2 [2, 3, 1]                 0
    3 [2, 3, 1]                 1
   22 [2, 3, 1]                -1
  -10 [1, 5, 10]               -1
    1 [1, 5, 10]                0
    5 [1, 5, 10]                1
    2 [1, 5, 10]               -1
   10 [1, 5, 10]                2
   22 [1, 5, 10]               -1
  -10 [10, 1, 5]               -1
    1 [10, 1, 5]                1
    5 [10, 1, 5]                2
    2 [1, 5, 10]               -1
   10 [10, 1, 5]                0
   22 [10, 1, 5]               -1
  -10 [5, 10, 1]               -1
    1 [5, 10, 1]                2
    5 [5, 10, 1]                0
    2 [1, 5, 10]               -1
   10 [5, 10, 1]                1
   22 [5, 10, 1]               -1
  -10 [1, 2, 3, 4]             -1
    1 [1, 2, 3, 4]              0
    2 [1, 2, 3, 4]              1
    3 [1, 2, 3, 4]              2
    4 [1, 2, 3, 4]              3
  -10 [1, 2, 3, 4]             -1
  -10 [4, 1, 2, 3]             -1
    1 [4, 1, 2, 3]              1
    2 [4, 1, 2, 3]              2
    3 [4, 1, 2, 3]              3
    4 [4, 1, 2, 3]              0
  -10 [4, 1, 2, 3]             -1
  -10 [3, 4, 1, 2]             -1
    1 [3, 4, 1, 2]              2
    2 [3, 4, 1, 2]              3
    3 [3, 4, 1, 2]              0
    4 [3, 4, 1, 2]              1
  -10 [3, 4, 1, 2]             -1
  -10 [2, 3, 4, 1]             -1
    1 [2, 3, 4, 1]              3
    2 [2, 3, 4, 1]              0
    3 [2, 3, 4, 1]              1
    4 [2, 3, 4, 1]              2
  -10 [2, 3, 4, 1]             -1
  -10 [1, 5, 8, 22]            -1
    1 [1, 5, 8, 22]             0
    5 [1, 5, 8, 22]             1
    8 [1, 5, 8, 22]             2
   22 [1, 5, 8, 22]             3
   10 [1, 5, 8, 22]            -1
  100 [1, 5, 8, 22]            -1
  -10 [22, 1, 5, 8]            -1
    1 [22, 1, 5, 8]             1
    5 [22, 1, 5, 8]             2
    8 [22, 1, 5, 8]             3
   22 [22, 1, 5, 8]             0
   10 [22, 1, 5, 8]            -1
  100 [22, 1, 5, 8]            -1
  -10 [8, 22, 1, 5]            -1
    1 [8, 22, 1, 5]             2
    5 [8, 22, 1, 5]             3
    8 [8, 22, 1, 5]             0
   22 [8, 22, 1, 5]             1
   10 [8, 22, 1, 5]            -1
  100 [8, 22, 1, 5]            -1
  -10 [5, 8, 22, 1]            -1
    1 [5, 8, 22, 1]             3
    5 [5, 8, 22, 1]             0
    8 [5, 8, 22, 1]             1
   22 [5, 8, 22, 1]             2
   10 [5, 8, 22, 1]            -1
  100 [5, 8, 22, 1]            -1
    5 [5, 1, 2, 3, 4]           0
    1 [5, 1, 2, 3, 4]           1
    2 [5, 1, 2, 3, 4]           2
    3 [5, 1, 2, 3, 4]           3
    4 [5, 1, 2, 3, 4]           4
    5 [4, 5, 1, 2, 3]           1
    1 [4, 5, 1, 2, 3]           2
    2 [4, 5, 1, 2, 3]           3
    3 [4, 5, 1, 2, 3]           4
    4 [4, 5, 1, 2, 3]           0
    5 [3, 4, 5, 1, 2]           2
    1 [3, 4, 5, 1, 2]           3
    2 [3, 4, 5, 1, 2]           4
    3 [3, 4, 5, 1, 2]           0
    4 [3, 4, 5, 1, 2]           1
    5 [2, 3, 4, 5, 1]           3
    1 [2, 3, 4, 5, 1]           4
    2 [2, 3, 4, 5, 1]           0
    3 [2, 3, 4, 5, 1]           1
    4 [2, 3, 4, 5, 1]           2
    5 [5, 77, 1, 2, 3]          0
   77 [5, 77, 1, 2, 3]          1
    1 [5, 77, 1, 2, 3]          2
    2 [5, 77, 1, 2, 3]          3
    3 [5, 77, 1, 2, 3]          4
    5 [5, 6, 1, 2, 3]           0
    6 [5, 6, 1, 2, 3]           1
    1 [5, 6, 1, 2, 3]           2
    2 [5, 6, 1, 2, 3]           3
    3 [5, 6, 1, 2, 3]           4
    5 [5, 6, 1, 2, 3, 4]        0
    6 [5, 6, 1, 2, 3, 4]        1
    1 [5, 6, 1, 2, 3, 4]        2
    2 [5, 6, 1, 2, 3, 4]        3
    3 [5, 6, 1, 2, 3, 4]        4
    4 [5, 6, 1, 2, 3, 4]        5

The reason why it's not O(n) is because in the case of O(n) it would mean that the performance of the algorithm would decrease linearly with the increase of the data, whilst in this case the performance decreases in a logarithmic fashion with the increase of the input data, as for each iteration we split the data set to smaller and smaller.

Chuck

Would it be "increase linearly with the increase of data" and "increase logarithmically with the increase of the input data"? Instead of "decrease"? – Irby

@user9476376 no, the performance always decreases, with the increase of data. Imagine processing 10 numbers versus procesing 1000000000000000 numbers. I'm trying to do a measuring of the algorithm by using the time module, but it seems I need a fair amount of data to display something in the order of seconds. I crashed my PC a few times doing this. – Chuck

print(search([5,6, 1, 2, 3, 4], 6)) returns -1 with your code. @Chuck it should return 1 – Chlorous

Thank you all for your help on this problem! – Irby

@Chuck if you don't mind me asking, what was your thought process for coming up with your conditional statements? How were you able to hit each case? – Irby

@user9476376 I started off by putting on paper the various potential cases that could appear in a list, for example: just one element, two elements, three elements (in this case it is clear which is low,mid and high), and then more than 3 elements. After that I rotated all the cases until I got all the combinations for them. After this I started building up the conditions that low/mid/high would meet if it the list was in a particular state and I built the conditions in the code off of that, specifying when to break or to alter the low/mid/high. – Chuck

Answer 2

Below is the fixed code. I ran it through leetcode and it passed.

Runtime: 52 ms, faster than 11.16% of Python online submissions for Search in Rotated Sorted Array. Memory Usage: 11.9 MB, less than 5.44% of Python online submissions for Search in Rotated Sorted Array.

This is O(log n) because we are reducing our problem size by half in every iteration. We either chose to pick right half of the array or left half of the array when we move our high/low in every iteration.
So your array size reduces like this; n, n/2, n/4, ..., 1 and it takes log n steps to reach from n to 1 by halving it every time.

class Solution(object):
def search(self, nums, target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = (low + high) // 2
        print(low,high,mid)

        if nums[mid] == target:
            return mid
        elif high==low:
            return -1
        elif nums[mid] <= nums[low] and nums[mid] <= nums[high] and nums[mid-1] >= nums[mid]:#mid is pivot

            if target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
        elif nums[mid] > nums[mid-1] and nums[high] > nums[mid]: #pivot to left of mid\
            if nums[mid] > nums[low]: #pivot at start index

                if target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            else:
                if target > nums[mid] and target <= nums[high]:
                    low = mid + 1
                elif target < nums[mid] or target >= nums[low]:
                    high = mid - 1
                else:
                    return -1
        elif nums[mid] >= nums[low] and nums[high] <= nums[mid]: #pivot to right of mid
            if target <= nums[high] or target > nums[mid] :
                low = mid + 1
            else:
                high = mid - 1
        else:
            return -1
    return -1

Chlorous