Dichotomy - starting and ending positions of elements (four methods)

Given an integer array nums arranged in ascending order and a target value target. Find the start and end positions of the given target value in the array.

If the target value target does not exist in the array, return [- 1, - 1].

Advanced:

  • Can you design and implement an algorithm with time complexity of O(log n) to solve this problem?

Example 1:

Input: num = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: num = [5,7,7,8,8,10], target = 6
Output: [- 1, - 1]

Example 3:

Input: num = [], target = 0
Output: [- 1, - 1]

analysis:

Since the nums array has been sorted, there is no need to sort this step. Obviously, the easiest solution is to traverse in sequence and find the first and last positions. However, this method is very unstable. If the target is in the front of nums and the number of the same value is less, it will be very fast. On the contrary, it may be very slow, but the slowest is O(n). It can be seen that the difference between slow and fast is very obvious.

#pragma region, violence method, sequential traversal
/*
Execution result: passed
 Execution time: 28 ms, beating 16.11% of users in all C + + submissions
 Memory consumption: 13.8 MB, beating 13.11% of users in all C + + submissions

Fastest time:
Execution time: 12 ms
 Memory consumption: 13.6 MB
*/
vector<int> searchRange(vector<int>& nums, int target) {
	if (nums.size() == 0)
		return vector<int>({ -1,-1 });
	int LIndex, RIndex;
	vector<int> retVec;
	bool Lfind = false, Rfind = false;
	for (int i = 0; i < nums.size(); ++i) {
		if (!Lfind) {
			if (nums[i] == target) {
				Lfind = true;
				LIndex = i;
			}
		}
		else {
			if (nums[i] != target) {
				Rfind = true;
				RIndex = i - 1;
				break;
			}
		}
	}
	if (Lfind) {
		retVec.push_back(LIndex);
		if (Rfind)
			retVec.push_back(RIndex);
		else
			retVec.push_back(nums.size() - 1);
	}else {
		retVec.push_back(-1);
		retVec.push_back(-1);
	}
	return retVec;
}
#pragma endregion

Is there any way to make the traversal process faster? We can approach from the head and tail to the middle, which reduces the number of cycles by half, and it is more ideal to deal with the case that the target is biased to one side of num. However, it is still very slow and even loses the super fast speed of the first method in extreme cases.

#pragma region, violence law, traversal on both sides
/*
Execution result: passed
 Execution time: 28 ms, beating 16.11% of users in all C + + submissions
 Memory consumption: 13.7 MB, beating 17.00% of users in all C + + submissions
*/
vector<int> searchRange(vector<int>& nums, int target) {
	if (nums.size() == 0)
		return vector<int>({ -1,-1 });
	int LIndex, RIndex;
	vector<int> retVec;
	bool Lfind = false, Rfind = false;
	int i = 0,j = nums.size()-1;
	while(i<=j) {
//		cout << "before(i = " << i << ",j = " << j << ")" << endl;
		if (!Lfind) {
			if (nums[i] == target) {
				Lfind = true;
				LIndex = i;
			}else
				++i;
		}
		if (!Rfind) {
			if (nums[j] == target) {
				Rfind = true;
				RIndex = j;
			}else
				--j;
		}
//		cout << "after(i = " << i << ",j = " << j << ")" << endl;
		if (Lfind && Rfind) 
			break;
	}
	if (Lfind) {
		retVec.push_back(LIndex);
		retVec.push_back(RIndex);
	}
	else {
		retVec.push_back(-1);
		retVec.push_back(-1);
	}
	return retVec;
}
#pragma endregion

The above two methods are helpless when the target is in the middle of nums. Therefore, it is thought that a point equal to target can be quickly found by dichotomy and spread to both sides with it as the center.

#pragma region binary search value and diffusion from the center
/*
Execution result: passed
 Execution time: 24 ms, beating 42.54% of users in all C + + submissions
 Memory consumption: 13.8 MB, beating 6.65% of users in all C + + submissions
*/
vector<int> searchRange(vector<int>& nums, int target) {
	//Dichotomy and diffusion from the middle
	if (nums.size() == 0)
		return vector<int>({-1,-1});
	vector<int> retVec;
	bool isFind = false;
	int MaxIndex = nums.size() - 1;
	int LIndex = 0;
	int RIndex = nums.size() - 1;
	int Index = (LIndex+RIndex) / 2;//Subscript of start position
	while(LIndex <= RIndex) {//Find a point equal to target
		if (target == nums[Index]) {
			isFind = true;
			break;
		}
		else if (target < nums[Index]) {
			RIndex = Index - 1;
			Index = (LIndex+RIndex) / 2;
		}
		else {
			LIndex = Index + 1;
			Index = (LIndex + RIndex) / 2;
		}
	}
	if (!isFind) {
		retVec.push_back(-1);
		retVec.push_back(-1);
	}
	else {
//		cout << "Find Index is --(" << Index << ")" << endl;
		bool lend = false, rend = false;
		for (int i = Index,j = Index;; i--, j++) {
			if (i >= 0 && nums[i] == target) {
				LIndex = i;
			}
			else { lend = true; }
			if (j <= MaxIndex && nums[j] == target) {
				RIndex = j;
			}
			else { rend = true; }
			if (lend && rend) {
				break;
			}
		}
		retVec.push_back(LIndex);
		retVec.push_back(RIndex);
	}
	return retVec;
}
#pragma endregion

In this way, it is much more stable and fast than the first two methods. However, it is not enough. The time complexity O(logn) is required in the advanced stage. Seeing logn, we can't help thinking of the dichotomy. We can use the dichotomy to find the left and right boundary LIndex and RIndex equal to the value of target respectively. However, when judging the dichotomy condition, it is different from the usual greater than or equal to less than. For the search process of LIndex, we can use the following judgment conditions.

if (nums[LIndex] < target) {//The target value is on the right
}else if (nums[LIndex] == target && (LIndex == 0 || nums[LIndex-1] < target)) {//Target value found
}else{}

Because the element with the smallest sequence number in the value equal to target either has no element in front of it (the sequence number is 0), or its previous element is less than target.

The code implementation is as follows:

#pragma region double dichotomy (separate cycle)
/*
Execution result: passed
 Execution time: 12 ms, beating 98.53% of users in all C + + submissions
 Memory consumption: 13.7 MB, beating 17.84% of users in all C + + submissions

Execution result: passed
 Execution time: 16 ms, beating 92.37% of users in all C + + submissions
 Memory consumption: 13.6 MB, beating 50.85% of users in all C + + submissions
*/
vector<int> searchRange(vector<int>& nums, int target) {//Double dichotomy (separate cycle)
	if (nums.size() == 0)
		return vector<int>({ -1,-1 });
	vector<int> retVec;
	int LLowIndex = 0, RLowIndex = 0;
	int LHighIndex = nums.size() - 1, RHighIndex = nums.size() - 1;
	int LIndex = (LLowIndex + LHighIndex) / 2;
	int RIndex = (RLowIndex + RHighIndex) / 2;
	bool Lfind = false, Rfind = false;
	while (LLowIndex <= LHighIndex) {
		if (nums[LIndex] < target) {//The target value is on the right
			LLowIndex = LIndex + 1;
			LIndex = (LLowIndex + LHighIndex) / 2;
		}
		else if (nums[LIndex] == target && (LIndex == 0 || nums[LIndex-1] < target)) {//Target value found
			Lfind = true;
			break;
		}
		else {//The target value is on the left
			LHighIndex = LIndex - 1;
			LIndex = (LLowIndex + LHighIndex) / 2;
		}
	}
	while (RLowIndex <= RHighIndex) {
		if (nums[RIndex] > target) {//The target value is on the left
			RHighIndex = RIndex - 1;
			RIndex = (RLowIndex + RHighIndex) / 2;
		}
		else if (nums[RIndex] == target && (RIndex == nums.size()-1 || nums[RIndex + 1] > target)) {//Target value found
			Rfind = true;
			break;
		}
		else {//The target value is on the right
			RLowIndex = RIndex + 1;
			RIndex = (RLowIndex + RHighIndex) / 2;
		}
	}
	if (Lfind) {
		retVec.push_back(LIndex);
		retVec.push_back(RIndex);
	}
	else {
		retVec.push_back(-1);
		retVec.push_back(-1);
	}
	return retVec;
}
#pragma endregion

It can be seen that at this time, the speed is very fast and relatively stable, and can be well controlled for nums in various postures. So, can it be faster? 🙀, Above, we used two while loops to find LIndex and RIndex respectively. Next, we use a loop to try.

#pragma region double dichotomy (merge cycle)
/*
Execution result: passed
 Execution time: 4 ms, beating 99.99% of users in all C + + submissions
 Memory consumption: 13.8 MB, beating 10.24% of users in all C + + submissions

The slowest time
 Execution time: 32 ms
 Memory consumption: 13.8 MB
*/
vector<int> searchRange(vector<int>& nums, int target) {//Double dichotomy (combined cycle)
	if (nums.size() == 0)
		return vector<int>({ -1,-1 });
	vector<int> retVec;
	int LLowIndex = 0, RLowIndex = 0;
	int LHighIndex = nums.size() - 1, RHighIndex = nums.size() - 1;
	int LIndex = (LLowIndex + LHighIndex) / 2;
	int RIndex = (RLowIndex + RHighIndex) / 2;
	bool Lfind = false, Rfind = false;
	while (LLowIndex <= LHighIndex || RLowIndex <= RHighIndex) {
		if (Lfind && Rfind)
			break;
		if (!Lfind) {
			if (nums[LIndex] < target) {//The target value is on the right
				LLowIndex = LIndex + 1;
				LIndex = (LLowIndex + LHighIndex) / 2;
			}
			else if (nums[LIndex] == target && (LIndex == 0 || nums[LIndex - 1] < target)) {//Target value found
				Lfind = true;
			}
			else {//The target value is on the left
				LHighIndex = LIndex - 1;
				LIndex = (LLowIndex + LHighIndex) / 2;
			}
		}
		if (!Rfind) {
			if (nums[RIndex] > target) {//The target value is on the left
				RHighIndex = RIndex - 1;
				RIndex = (RLowIndex + RHighIndex) / 2;
			}
			else if (nums[RIndex] == target && (RIndex == nums.size() - 1 || nums[RIndex + 1] > target)) {//Target value found
				Rfind = true;
			}
			else {//The target value is on the right
				RLowIndex = RIndex + 1;
				RIndex = (RLowIndex + RHighIndex) / 2;
			}
		}
	}
	if (Lfind) {
		retVec.push_back(LIndex);
		retVec.push_back(RIndex);
	}else {
		retVec.push_back(-1);
		retVec.push_back(-1);
	}
	return retVec;
}
#pragma endregion

Wuhu 🛫!

Tags: Algorithm

Posted by ryansmith44 on Wed, 04 May 2022 02:29:00 +0300