34. Search for a Range

Description:

https://leetcode.com/problems/search-for-a-range/#/description

Algorithm:

1. Use find() to determine whether the target is in the array.
2. Left = 0, right = size – 1;
3. Squeeze left and right to find middle s.t. nums[middle] == target
4. Squeeze left and middle to find left s.t.  nums[left] == target
5. Squeeze right and middle to find right s.t.  nums[right] == target

Code:


class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector <int> result;
vector<int>::iterator iter = std::find(nums.begin(), nums.end(), target);
if (iter == nums.end())
{
result.push_back(-1);
result.push_back(-1);
return result;
}

int left = 0;
int right = nums.size() - 1;
int middle_left, middle_right;
while (nums[left] < nums[right])
{
int middle = (left + right) / 2;
if (nums[middle] < target)
left = middle + 1;
else if (nums[middle] > target)
right = middle - 1;
else
{
int middle_save = middle;
while (nums[left] < target)
{
middle_left = (middle + left) / 2;
if (nums[middle_left] < target)
left = middle_left + 1;
else
middle = middle_left - 1;
}

middle = middle_save;
while (nums[right] > target)
{
middle_right = (middle + right) / 2;
if (nums[middle_right] > target)
right = middle_right - 1;
else
middle = middle_right + 1;
}
}
}
result.push_back(left);
result.push_back(right);
return result;
}
};

Timing: beat 47.5%. 9ms

Best is 6ms.

Code for 6ms algorithm:


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

return res;
}
};