Menu
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!
714
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.
143
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
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
