Search for a Range


  • 0
    S
    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
    		int ret = binarySearch(nums, target);
    		if (ret == -1){
    			vector<int> result = { -1, -1 };
    			return result;
    		}
    		else{
    			int i, j;
    			for (i = ret; i - 1 >= 0 && nums[i - 1] == target; i--);
    			for (j = ret; j + 1 < nums.size() && nums[j + 1] == target; j++);
    			vector<int> result = {i, j};
    			return result;
    		}
    	}
    	//binary search
    	int binarySearch(vector<int>& nums, int target)
    	{
    		int middle, low = 0, high = nums.size() - 1;
    		while (low <= high){
    			middle = low + (high - low) / 2;
    			if (nums[middle] < target)
    				low = middle + 1;
    			else if (nums[middle] > target)
    				high = middle - 1;
    			else
    				return middle;
    		}
    		return -1;
    	}
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.