###### tags: `Leetcode` `medium` `binary search` `python` `Top 100 Liked Questions`

# 34. Find First and Last Position of Element in Sorted Array

## [題目連結:] https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

## 題目:
Given an array of integers ```nums``` sorted in non-decreasing order, find the starting and ending position of a given ```target``` value.

If target is not found in the array, return ```[-1, -1]```.

You must write an algorithm with ```O(log n)``` runtime complexity.

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

**Example 3:**

Input: nums = [], target = 0
Output: [-1,-1]

## 解題想法:
* 題目要求，找target在數組中最左邊與最右邊出現的位置，若無，返回-1
* 看到O(log n) runtime complexity: Binary Search
* 分別做兩次binary Search，
* 第一次求最左邊出現的位置:
* if target==nums[mid]:
* firstPos=mid
* **right=mid-1** 往左半邊移動
* 第二次求最右邊出現的位置:
* if target==nums[mid]:
* lastPos=mid
* **left=mid+1** 往右半邊移動

## Python:

class Solution(object):
    def searchRange(self, nums, target):
        return [self.findFirst(nums,target),self.findLast(nums,target)]

    def findFirst(self,nums,target):
        left = 0
        right = len(nums)-1
        firstPos = -1
        while left<=right:
            mid = (left+right)//2
            if target==nums[mid]:
                firstPos = mid
                #格局移置左半check
                right = mid-1
            elif target<nums[mid]:
                right = mid-1
            else:
                left = mid+1
        return firstPos

    def findLast(self,nums,target):
        left = 0
        right = len(nums)-1
        lastPos = -1
        while left<=right:
            mid = (left+right)//2
            if target==nums[mid]:
                lastPos=mid
                #往右半check
                left = mid+1
            elif target<nums[mid]:
                right= mid-1
            else:
                left =mid+1
        return lastPos


if __name__ == '__main__':
    result = Solution()
    nums = [5,7,7,8,8,10]
    target = 8
    ans = result.searchRange(nums,target)
    print(ans)
#Input: nums = [5,7,7,8,8,10], target = 8
#Output: [3,4]