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

解法一 - Binary Search

這題只要求在 O(logn) 時間內做完，所以我們可以考慮用兩次 binary search，一次搜尋 range 的起始點，一次搜尋 range 的終點：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> pos(2, -1);
        if(nums.empty()) return pos;

        // Search the start of range
        int start=0, mid, end = nums.size()-1;

        while(start+1 < end) {
            mid = start + (end-start)/2;

            // Keep searching forward when nums[mid] == target 
            if(nums[mid] == target) end = mid;
            else if(nums[mid] < target) start = mid;
            else end = mid;
        }

        if(nums[start] == target) pos[0] = start;
        else if(nums[end] == target) pos[0] = end;

        // Search the end of range
        start = 0, end = nums.size()-1;

        while(start+1 < end) {
            mid = start + (end-start)/2;

            // Keep searching backward when nums[mid] == target
            if(nums[mid] == target) start = mid;
            else if(nums[mid] < target) start = mid;
            else end = mid;
        }

        if(nums[end] == target) pos[1] = end;
        else if(nums[start] == target) pos[1] = start;

        return pos;
    }
};

實做起來的效率其實還不錯：

Runtime: 4 ms, faster than 99.57% of C++ online submissions for Find First and Last Position of Element in Sorted Array. Memory Usage: 10.3 MB, less than 68.10% of C++ online submissions for Find First and Last Position of Element in Sorted Array.