Problem :

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array


My Solution :

class Solution:
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""

def search(low, high, target):
while low < high:
mid = (low + high) // 2
if nums[mid] < target:
low = mid + 1
else:
high = mid
return low

left = search(0, len(nums), target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = search(left+1, len(nums), target+1)-1
return [left, right]


Comment :

binary search를 수행하는데, high를 len(nums)-1이 아니라 len(nums)로 잡은게 핵심이다. 그로 인해 right 값을 target+1의 index - 1로 구할 수 있게 된다.