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].

Example 1:


Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:


Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Difficulty: interview

Starter code:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:


Solutions:
class Solution:
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         start = self.firstGreaterEqaul(nums, target)
         if start==len(nums) or nums[start]!=target:
             return [-1, -1]
         return [start, self.firstGreaterEqaul(nums, target+1)-1]
     def firstGreaterEqaul(self, nums, target):
         lo, hi = 0, len(nums)
         while lo<hi:
             mid = (hi+lo)//2
             if nums[mid]<target:
                 lo = mid + 1
             else:
                 hi = mid
         return lo

class Solution:
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         import bisect
         lo=bisect.bisect_left(nums,target)
         if target in nums[lo:lo+1]:
             hi=bisect.bisect(nums,target)-1
             return [lo, hi]
         else:
             return [-1, -1]

class Solution:
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         result = []
         left, right = 0, len(nums)-1
         while left <= right:
             mid = (left+right) // 2
             print(('mid:', mid))
             if nums[mid] == target:
                 print('hello')
                 if mid == 0 or nums[mid-1] < target:
                     result.append(mid)
                     break
                 else:
                     right = mid -1
             elif nums[mid] < target:
                 left = mid+1
             else:
                 right = mid-1
         left, right = 0, len(nums)-1
         while left <= right:
             mid = (left+right) // 2
             if nums[mid] == target:
                 if mid == len(nums)-1 or nums[mid+1] > target:
                     result.append(mid)
                     break
                 else:
                     left = mid + 1
             elif nums[mid] < target:
                 left = mid+1
             else:
                 right = mid-1
         if len(result) == 0:
             return [-1, -1]
         return result
         



 
 class Solution:
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         
         if len(nums) == 0:
             return [-1, -1]
 
         nums = [target - 1] + nums + [target + 1]
 
         lbound = -1
 
         l, r = 1, len(nums) - 2
 
         while l <= r:
 
             m = (l + r)//2
 
             if nums[m] == target and nums[m - 1] < target:
                 lbound = m
                 break
 
             if nums[m] < target:
                 l = m + 1
             else: # nums[m] >= target:
                 r = m - 1
 
         if lbound == -1:
             return [-1, -1]
 
         rbound = -1
         l, r = 1, len(nums) - 2
 
         while l <= r:
 
             m = (l + r)//2
 
             if nums[m] == target and nums[m + 1] > target:
                 rbound = m
                 break
 
             if nums[m] <= target:
                 l = m + 1
             else: # target < nums[m]
                 r = m - 1
 
         return [lbound - 1, rbound - 1]
 


class Solution:
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         if not nums:
             return [-1,-1]
         a=self.findLeft(nums,target)
         b=self.findRight(nums,target)
         if nums[a]!=target:
             return [-1,-1]
         return [a,b]
         
     def findLeft(self,nums,target):
         low,high=0,len(nums)-1
         while low<high:
             mid=(low+high)//2
             
             if nums[mid]>=target:
                 high=mid
             else:
                 low=mid+1
         return low
     
     def findRight(self,nums,target):
         low,high=0,len(nums)-1
         while low<high:
             mid=(low+high)//2+1
             if nums[mid]>target:
                 high=mid-1
             else:
                 low=mid
         return high
     
     


class Solution:
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         #m = int(len(nums)/2)
         #upper, lower = nums[:m], nums[m:]
         s, e = -1, -1
         l, u = 0, len(nums)-1
         if not nums or target > nums[u] or target < nums[l]:
             return [s, e]
         m = int((l+u)/2)
         while u >= l:
             if nums[m] > target:
                 if m == u:
                     break
                 u = m
                 #if int((l+u)/2) == u:
                 #    break
                 m = int((l+u)/2)
             elif nums[m] < target:
                 l = m
                 if int((l+u)/2) == l:
                     m = l+1
                 else:
                     m = int((l+u)/2)
             else:
                 s = e = m
                 while 0 < s and nums[s-1] == nums[s]:
                     s-=1
                 while e < len(nums)-1 and nums[e+1] == nums[e]:
                     e+=1
                 break
         return [s, e]


class Solution:
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         s, e = -1, -1
         l, u = 0, len(nums)
         if not nums or target > nums[u-1] or target < nums[l]:
             return [s, e]
         m = (l+u)//2
         while u > l:
             if nums[m] > target:
                 u = m
                 m = (l+u)//2
             elif nums[m] < target:
                 l = m+1
                 m = (l+u)//2
             else:
                 s = e = m
                 while 0 < s and nums[s-1] == nums[s]:
                     s-=1
                 while e < len(nums)-1 and nums[e+1] == nums[e]:
                     e+=1
                 break
         return [s, e]


class Solution:
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         left = 0; right = len(nums) - 1
         while left <= right:
             mid = int((left + right) / 2)
             if nums[mid] > target:
                 right = mid - 1
             elif nums[mid] < target:
                 left = mid + 1
             else:
                 list = [0, 0]
                 if nums[left] == target: list[0] = left
                 if nums[right] == target: list[1] = right
                 for i in range(mid, right+1):
                     if nums[i] != target: list[1] = i - 1; break
                 for i in range(mid, left-1, -1):
                     if nums[i] != target: list[0] = i + 1; break
                 return list
         return [-1, -1]

class Solution:
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """           
         def findBoundary(nums, left, right, target):
             [l_boundary, r_boundary] = [len(nums), -1]
             middle = int((left+right)/2)
             if left <= right and nums[left] <= target and nums[right] >= target:
                 if nums[left] == target:
                     l_boundary = left
                 if nums[right] == target:
                     r_boundary = right
                 if nums[middle] < target:
                     [l_boundary, r_boundary] = findBoundary(nums, middle+1, right, target)
                 elif nums[middle] > target:
                     [l_boundary, r_boundary] = findBoundary(nums, left, middle, target)
                 else:
                     l_boundary = min(findBoundary(nums, left, middle-1, target)[0], middle)
                     r_boundary = max(findBoundary(nums, middle+1, right, target)[1], middle)
             return [l_boundary, r_boundary]
         
         boundary = findBoundary(nums, 0, len(nums)-1, target)
         if boundary[1] == -1:
             return [-1, -1]
         else:
             return boundary
 
                 


class Solution:
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         # self made, two times binary search, beats 93%
         if not nums:
             return [-1, -1]
         # find left most index
         l, r = 0, len(nums) - 1
         while l + 1 < r:
             mid = l + (r - l) // 2
             if nums[mid] < target:
                 l = mid
             else:
                 r = mid
         left = l if nums[l] == target else r
         # find right most index
         l, r = 0, len(nums) - 1
         while l + 1 < r:
             mid = l + (r - l) // 2
             if nums[mid] <= target:
                 l = mid
             else:
                 r = mid
         right = r if nums[r] == target else l
         if nums[left] != target:
             return [-1, -1]
         
         return [left, right]


class Solution:
     def getRange(self, nums, index):
         prev = index - 1 
         after = index + 1
         while prev >= 0 and nums[prev] == nums[index]:
             prev -= 1
         while after < len(nums) and nums[after] == nums[index]:
             after += 1
         return [prev + 1, after -1]
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         if nums == []: return [-1, -1]
         m = int(len(nums)/2)
         if target == nums[0]:   return self.getRange(nums, 0)
         elif target == nums[-1]: return self.getRange(nums, len(nums) -1)
         elif target == nums[m]: return self.getRange(nums, m)
         else:
             if target < nums[0] or target > nums[-1]:   return [-1,-1]
             elif target < nums[m]:
                 return self.searchRange(nums[: m], target)
             else:
                 tempRange = self.searchRange(nums[m:], target)
                 if tempRange[0] == -1:  return [-1, -1]
                 else: return [r + m  for r in tempRange]

class Solution:
     def getRange(self, nums, index):
         prev = index - 1 
         after = index + 1
         while prev >= 0 and nums[prev] == nums[index]:
             prev -= 1
         while after < len(nums) and nums[after] == nums[index]:
             after += 1
         return [prev + 1, after -1]
     def getIndex(self, nums, target):
         if nums == [] or target < nums[0] or target > nums[-1]:  return -1
         if target == nums[0]:  return 0
         if target == nums[-1]:  return len(nums) -1
         
         m = int(len(nums)/2)
         
         if target < nums[m]:
             return self.getIndex(nums[:m], target) 
         else:
             return -1 if self.getIndex(nums[m: ], target) < 0 else self.getIndex(nums[m: ], target) + m
             
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         index = self.getIndex(nums, target)
         if index == -1: return [-1, -1]
         else:
             return self.getRange(nums, index)


class Solution:
     def getRange(self, nums, index):
         prev = index
         after = index
         while prev >= 0 and nums[prev] == nums[index]:
             prev -= 1
         while after < len(nums) and nums[after] == nums[index]:
             after += 1
         return [prev + 1, after -1]
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         if nums == []: return [-1, -1]
         m = int(len(nums)/2)
         if target == nums[0]:   return self.getRange(nums, 0)
         elif target == nums[-1]: return self.getRange(nums, len(nums) -1)
         elif target == nums[m]: return self.getRange(nums, m)
         else:
             if target < nums[0] or target > nums[-1]:   return [-1,-1]
             elif target < nums[m]:
                 return self.searchRange(nums[: m], target)
             else:
                 tempRange = self.searchRange(nums[m:], target)
                 if tempRange[0] == -1:  return [-1, -1]
                 else: return [r + m  for r in tempRange]

class Solution:
     def searchRange(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[int]
         """
         start = 0
         end = len(nums) - 1
         mid = 0
         ans = [-1, -1]
         while (start <= end):
             mid = int((start + end) / 2)
             if (nums[mid] == target):
                 ans[0] = mid  
                 ans[1] = mid  
                   
                 i = mid - 1  
                 while i >= 0 and nums[i] == target:  
                     ans[0] = i  
                     i -= 1  
                   
                 i = mid + 1  
                 while i < len(nums) and nums[i] == target:  
                     ans[1] = i  
                     i += 1  
                       
                 break  
             elif (nums[mid] > target):
                 end = mid - 1
             else:
                 start = mid + 1
             
         return ans