Problem
Given an array of integers nums
sorted in ascending order, find the starting and ending position of a given target
value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1]
.
Examples
1 | Input: nums = [5,7,7,8,8,10], target = 8 |
1 | Input: nums = [5,7,7,8,8,10], target = 6 |
Solution1
Method: Binary Search with left_flag
Time Complexity: O(log n)
Space Complexity: O(1)
1 | class Solution: |
Solution2
Method: Two Binary Search
Time Complexity: O(log n)
Space Complexity: O(log n)
1 | def searchRange(self, nums, target): |
Solution3
Method: Built-in bisect
Time Complexity: O(log n)
Space Complexity: O(log n)
1 | class Solution: |