[LeetCode][Python3] 34. Find First and Last Position of Element in Sorted Array

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로 구할 수 있게 된다.