###### tags: `LeetCode` `Medium` `Binary Search`
# LeetCode #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/)
### (Medium)

給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。

如果數組中不存在目標值 target，返回 [-1, -1]。

---
題目要求時間複雜度為O(logn), 可以使用upper_bound, lower_bound-1, 或是自己實作二元搜尋。

對於二元搜尋來說, 找到目標值在數組中的起始位置的方法為只有當中間元素小於目標值時, 才將左邊位置調成中間位置(因為如果判斷條件為小於等於, 則當target值等於中間元素值時, 會將左邊位置調為中間位置+1, 不符合找到target值的第一個位置的敘述), 如下圖

[5,7,8,8,8,10], target=8
       ↑ 

此時若將l設為mid+1, 則不可能找到位置2的8。

接下來找目標數在數組中的中止位置, 只要找到數組中第一個比目標數大的樹的位置, 再將該位置-1即可得到。

---

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans = {-1,-1};
        if(nums.size()){
            int l=0, h=nums.size();
            while(l<h){
                int m = l+(h-l)/2;
                if(nums[m]<target)l=m+1;
                else h=m;
            }
            if(l>=nums.size()||nums[l]!=target)return ans;
            else ans[0]=l;
            l=0, h=nums.size();
            while(l<h){
                int m = l+(h-l)/2;
                if(nums[m]<=target)l=m+1;
                else h=m;
            }
            if(nums[l-1]==target)ans[1]=l-1;
        }
        return ans;
    }
};