# 34. Find First and Last Position of Element in Sorted Array
#### Difficulty: Medium
link: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

### 1. Binary Search
#### $O(log\ n)$ runtime, $O(1)$ space

這題用來練習bisect套件，記得找出來的index最大值是len(arr)，所以arr[index]可能會out of index，需要先檢查。

##### python

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binary_search(arr, val, leftside=True):
            left, right = 0, len(arr)
            while left < right:
                mid = left + (right - left) // 2
                if (leftside and val <= nums[mid]) or (not leftside and val < nums[mid]):
                    right = mid
                else:
                    left = mid + 1
            return left
        
        left = binary_search(nums, target)
        right = binary_search(nums, target, False)
        if left == len(nums) or nums[left] != target:
            return [-1, -1]
        return [left, right-1]

import bisect
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = bisect.bisect_left(nums, target)
        right = bisect.bisect_right(nums, target)
        if left == len(nums) or nums[left] != target:
            return [-1, -1]
        return [left, right-1]

邊界設定為0 ~ len(nums) - 1，就會是比較複雜的兩次binary search作法。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        ans = [-1, -1]
        if not nums:
            return ans
        
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid
            else:
                left = mid + 1
        
        if nums[left] != target:
            return ans
        else:
            ans[0] = left
        
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > target:
                right = mid
            else:
                left = mid + 1
        
        if nums[left] == target:
            ans[1] = left
        else:
            ans[1] = left - 1
        
        return ans

改用bisect套件

import bisect
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        ans = [-1, -1]
        if not nums:
            return ans
        
        left = bisect.bisect_left(nums, target, hi=len(nums)-1)
        if nums[left] != target:
            return ans
        else:
            ans[0] = left
        
        left = bisect.bisect_right(nums, target, lo=left, hi=len(nums)-1)
        if nums[left] == target:
            ans[1] = left
        else:
            ans[1] = left - 1
        
        return ans

###### tags: `leetcode`