Links
Go to my solution
Go to the question on LeetCode
My Thoughts
What Went Well
I created a solution, although not optimal, and discovered how to achieve O(log n) time complexity.
What Went Wrong
I did not realize that performing a binary search on a sorted array resulted in O(log n) time complexity, and I believed implementing a binary search would be inefficient.
How I Can Improve
I need to keep learning. As long as I keep posting, analyzing optimal solutions, and can at least get a functioning solution, then I am happy.
Comments
The truly optimal solution has far worse statistics than my “Pythonic” solution. I hope this trend does not continue because it was very helpful in alerting me if I had a poor solution and should optimize it.
Algorithm Description
Binary Search - A search algorithm that repeatedly halves the search interval until the target variable is found at the middle index.
Visual Examples
Binary search being performed on an array that contains the target, click to view
Binary search being performed on an array that does not contain the target, click to view
Optimal Solution Statistics
Time Complexity
O(log n) - The program performs a modified version of binary search O(n log n) on the input list, but the input list is already sorted, resulting in the O(log n) time complexity. With the modifications to the binary search algorithm, we can achieve the O(log n) time complexity due to the list having unique elements and being sorted.
Space Complexity
O(1) - The number of variables created is independent from the number of elements in the input list, resulting in the O(1) space complexity.
Optimal Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums)-1
while l <= r:
mid = l+(r-l)//2
if nums[mid] == target: return mid
if nums[mid] >= nums[l]:
if nums[l] <= target < nums[mid]:
r = mid -1
else:
l = mid+1
else:
if nums[mid] < target <= nums[r]:
l = mid+1
else:
r = mid-1
return -1
Original Solution Statistics
Time Spent Coding
1 minute
Time Complexity
O(n) - In the worst-case scenario, this solution would visit all the elements in the list, resulting in the O(n) time complexity.
Space Complexity
O(1) - No new variables were created, resulting in the O(1) space complexity.
Runtime Beats
98.72% of other submissions
Memory Beats
89.90% of other sumbissions
Solution
1
2
3
4
5
class Solution:
def search(self, nums: List[int], target: int) -> int:
if target in nums:
return nums.index(target)
return -1