leetcode 34 -- Search for a Range

Search for a Range

题目：
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,

---

题意：
给予一个已排序的数组，找到给定target的第一次和最后一次出现的位置。时间复杂度要求为log(n)

---

思路：
二分即可，找到目标值后，定义两个index，找寻该target第一次和最后一次出现的位置。注意一些边界条件即可。

---

代码：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int>ret = {-1, -1};
        if(nums.size() == 1){
            if(nums[0] == target){
                ret[0] = 0;
                ret[1] = 0;
                return ret;
            }
        }else if(nums.size() == 0){
            return ret;
        }
        int left = 0;
        int right = nums.size()-1;
        int mid = 0;
        while(left <= right){
            mid = left+(right-left)/2;
            if(nums[mid] == target){
                int index1 = mid;
                int index2 = mid;
                while(nums[index1+1] == target){
                    if(index1 < nums.size()-1)
                        index1++;
                    else
                        break;
                }
                while(nums[index2-1] == target){
                    if(index2 > 0)
                        index2--;
                    else
                        break;
                }
                ret[0] = index2;
                ret[1] = index1;
                return ret;
            }else if(nums[mid] < target){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return ret;
    }
};