A small trick-convert this problem to search a double number in an int list


  • 2
    B

    Consider the case where nums = [5, 7, 7, 8, 8, 10], target = 8, if we search target double number 8.1, the binary search return the index of 10, if we search double number 7.9, the binary search return the index of last 7.
    it's easy, just let the binary search return the index where the double number should be in the int list), the the index of begin and end of target is find.done.

    vector<int> searchRange(vector<int>& nums, int target) {
        int right = binary_search(nums, double(target)+0.1);
    	if(right == 0)
    		return 0;
    	if(nums[right-1] != target)
    		return 0;
    	int left = binary_search(nums, double(target)-0.1);
    	return right-left+1;
    }
    
    void binary_search(vector<int> nums, double target)
    {
    	int low = 0, high = nums.size()-1, middle;
    	while(low<=high)
    	{
    		middle = low + (high-low)/2;
    		if(double(nums[middle]) > target)
    			high = middle - 1;
    		else
    			low = middle + 1;
    	}
    	return low;
    }

  • 0
    M

    This is a very smart and elegant trick.


Log in to reply
 

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