34. Find First and Last Position of Element in Sorted Array
1. Description
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
2. Follow Up
Could you write an algorithm with O(log n) runtime complexity?
3. Example
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
4. Constraints
- 0 <= nums.length <= $10^5$
- $-10^9$ <= nums[i] <= $10^9$
- nums is a non-decreasing array.
- $-10^9$ <= target <= $10^9$
5. Solutions
My Accepted Solution(Follow Up)
n = i_nums.size()
Time complexity: O($lg_2n$)
Space complexity: O(1)
class Solution {
private:
int binarSearch(const vector<int> &i_nums, int target, bool leftFlag) // leftFlag == true means we want to find left border
{
for(int left = 0, right = i_nums.size()-1; left <= right; )
{
int middle = (left + right) / 2;
if(i_nums[middle] == target)
{
if(leftFlag)
{
if(middle == 0 || i_nums[middle-1] != target)
return middle;
else
right = middle;
}
else
{
if(middle == i_nums.size()-1 || i_nums[middle+1] != target)
return middle;
else
left = (middle == left ? middle + 1 : middle);
// when we enter this branch, that means we have more than one target
// but we need to be aware of the contion of infinite loop, such as left = 0, right = 1
// that's because for int, 0 / 2 == 0, and 1 / 2 == 0, so we need to check whether left keep the same value
}
}
else if(i_nums[middle] < target)
left = middle + 1;
else
right = middle - 1;
}
return -1;
}
public:
// vector<int> searchRange(vector<int>& nums, int target)
vector<int> searchRange(const vector<int> &i_nums, int target)
{
return vector<int>{binarSearch(i_nums, target, true)
, binarSearch(i_nums, target, false)
};
}
};
4.1 Binary Search - Merge Two Processes
n = i_nums.size()
Time complexity: O($lg_2n$)
Space complexity: O(1)
class Solution
{
public:
// vector<int> searchRange(vector<int>& nums, int target)
int search(const vector<int> &i_nums, int target)
{
for(int left = 0, right = i_nums.size() - 1; left <= right; )
{
int middle = (left+right) / 2;
if(i_nums[middle] == target) return middle;
if(i_nums[middle] < i_nums[right])
{
if(i_nums[middle] < target && i_nums[right] >= target)
left = middle + 1;
else
right = middle - 1;
}
else
{
if(i_nums[left] <= target && i_nums[middle] > target)
right = middle - 1;
else
left = middle + 1;
}
}
return -1;
}
};