Search in Rotated Sorted Array in O(log n) time
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
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.