LeetCode Search for a Range

LeetCode Search for a Range

Given an array of integers sorted in ascending order, 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,
return [3, 4].


本题要在一个有序数组中求一个数出现的下标区间,如果该数不在数组中,返回[-1,-1],要求用O(lgn)时间复杂度。

很明显用两次二分搜索找到该数的上下区间即可,可以认为是二分搜索的综合题。下界就是第一个不小于target的位置,所以当找到中间值和target相等时,我们要继续往左找。上界就是最后一个不大于target的位置,所以当找到中间值和target相等时,我们要继续往右找。理清了这个思路之后就很好写代码了,如下:

class Solution {
private:
	int lowerbound(vector<int>& nums, int target) {
		int l = 0, r = nums.size() - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (nums[m] < target)l = m + 1;
			else if (nums[m] >= target)r = m - 1;
		}
		return l;
	}

	int upperbound(vector<int>& nums, int target) {
		int l = 0, r = nums.size() - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (nums[m] <= target)l = m + 1;
			else if (nums[m] > target)r = m - 1;
		}
		return r;
	}
public:
	vector<int> searchRange(vector<int>& nums, int target) {
		int lower = lowerbound(nums, target), upper = upperbound(nums, target);
		if (lower <= upper)return vector<int>({ lower, upper });
		else return vector<int>({ -1,-1 });
	}
};

本代码提交AC,用时9MS。

注意一点,为啥lowerbound是返回l,而upperbound是返回r呢,对于lowerbound,我们想象一下当中值等于target时,我们不停的往左走,即r=m-1,直到l<=r不再满足,即此时r已经小于l了,也就是说r往左走过头了,使得r对应的值已经小于target了,但此时l对应的值还是等于target,所以根据lowerbound的定义,我们返回l。对于uppperbound也类似,当中值等于target时,不停往右走,即l=m+1,直到不满足l<=r,此时l对应的值已经大于target,而r对应的值还是等于target的,根据upperbound的定义,我们返回r。

其实,STL中已经实现了lower_boundupper_bound其lower_bound和上文的lowerbound含义是一致的,upper_bound稍有不同,STL中的upper_bound是返回第一个大于target的位置,比上文的upperbound要大一个位置。所以如果借助STL的算法,需要对upper_bound返回的位置减1。代码如下:

class Solution {
public:
	vector<int> searchRange(vector<int>& nums, int target) {
		if (nums.size() == 0)return vector<int>({ -1,-1 });
		vector<int>::iterator lower = lower_bound(nums.begin(), nums.end(), target), upper = upper_bound(nums.begin(), nums.end(), target) - 1;
		if (lower <= upper)return vector<int>({ lower - nums.begin(), upper - nums.begin() });
		else return vector<int>({ -1,-1 });
	}
};

本代码提交AC,用时16MS。貌似STL中的实现也是O(lgn)的,看来性能还是有所差别。

One thought on “LeetCode Search for a Range

  1. Pingback: LeetCode First Bad Version | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *