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]

Source: leetcode | Difficulty: MEDIUM_HARD

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


Solutions:
class Solution:

	def searchRange(self, nums, target):
		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):
		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):
		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):
		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):
		(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
				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):
		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):

		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):
		if not nums:
			return [-1, -1]
		(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
		(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):
		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)
		elif 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):
		index = self.getIndex(nums, target)
		if index == -1:
			return [-1, -1]
		else:
			return self.getRange(nums, index)


class Solution:

	def searchRange(self, nums, target):
		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