---
# System prepended metadata

title: LeetCode 34. Find First and Last Position of Element in Sorted Array
tags: [Leetcode]

---

# LeetCode 34. Find First and Last Position of Element in Sorted Array
[34. Find First and Last Position of Element in Sorted Array](leetcode_url) (<font color=#FFB800>Medium</font> 44.0%)

<!-- 
(<font color=#00AF9B>Easy</font> 53.8%) 
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
 -->
    
- 限制 :

    <ul>
    <li><code>0 <= nums.length <= 10⁵</code></li>
    <li><code>-10⁹ <= nums[i] <= 10⁹</code></li>
    <li><code>nums is a non-decreasing array.</code></li>
    <li><code>-10⁹ <= target <= 10⁹</code></li>
    </ul>

- Solution
    這題也不是難題，就是要去看左右邊，並且要注意空陣列，其餘還好，就是一個 binary search 的題目。
    - 時間複雜度: $O(lg(n))$
    - 空間複雜度: $O(1)$

- 程式碼
    ```c++=
    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            int min_index = 0, max_index = nums.size()-1;
            int mid_index;
            if(nums.size() > 0)
            {
                while(min_index <= max_index)
                {
                    mid_index = (max_index - min_index) /2 + min_index;
                    if (nums[mid_index] == target) break;
                    if (nums[mid_index] < target) min_index = mid_index + 1;
                    else if (nums[mid_index] > target ) max_index = mid_index - 1;
                }
            }

            int left_index = -1, right_index = -1;
            if(nums.size() > 0 && nums[mid_index] == target)
            {
                for(int i = mid_index; i>=0 && nums[i] == nums[mid_index]; i--)
                {
                    right_index = i;
                }

                for(int i = mid_index;i < nums.size() && nums[i] == nums[mid_index]; i++)
                {
                    left_index = i;
                }
            }
            vector<int>results{right_index, left_index};
            return results;
        }
    };
    ```
</details>