Find First And Last Position of Element in Sorted Array is a classic coding interview question asked by many big companies such as Google, Facebook, etc. This question is based on Binary Search.
Given an array of integers 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].
Note: The solution to this question must be in O(log n) complexity. Also, the array may contain duplicate numbers in ascending order.
Find First And Last Position of Element in Sorted Array Solution C++/Python
I am going to solve this question in three different languages. Here the Binary Search Algorithm is used. But to solve this specific question we are going to use the modified binary search algorithm to get the last and first positions.
Algorithm:
I am going to take the low as index 0 and the high as the last index of the array. Then I will be calculating the mid of the array and in the first binary search, I will only compare low and move it as required.
So, after the first binary search, you will get the index of the first occurrence of the target number. If you do not get the first occurrence in the first binary search then you can simply return the array with value [-1,-1].
But if the first occurrence is found then the high variable is assigned again with the last index of the array and in the second binary search, only the high variable will be assigned as required after comparison.
Once the search is complete you have the variable high as an index of the last occurrence of the target value in the array.
Store that value in the result array and return the resulting array and that will be your answer to the question.
Explanation
First, let’s find the left boundary of the range. We initialize the range to [i=0, j=n-1]. In each step, calculate the middle element [mid = (i+j)/2]. Now according to the relative value of A[mid] to target, there are three possibilities:
- If A[mid] < target, then the range must begins on the right of mid (hence i = mid+1 for the next iteration)
- If A[mid] > target, it means the range must begins on the left of mid (j = mid-1)
- If A[mid] = target, then the range must begins on the left of or at mid (j= mid)
Since we would move the search range to the same side for cases 2 and 3, we might as well merge them as one single case so that less code is needed:
2*. If A[mid] >= target, j = mid;
Surprisingly, 1 and 2* are the only logic you need to put in the loop while (i < j). When the while loop terminates, the value of i/j is where the start of the range is. Why?
No matter what the sequence originally is, as we narrow down the search range, eventually we will be in a situation where there are only two elements in the search range.
The above explanation provides the complete solution for the problem Find First And Last Position of Element in Sorted Array. Let us see the coding solution for this problem below.
Solution in C++
class Solution {
public:
vector<int> searchRange(vector<int>& givenArray, int target) {
vector<int> result;
result.push_back(-1);
result.push_back(-1);
int arraySize = givenArray.size();
int high = arraySize-1;
if(arraySize==0) return result;
int low = 0;
while(low<high){
int mid = (low+high)/2;
if(target > givenArray[mid])
low = mid + 1;
else
high = mid;
}
if(givenArray[low]!=target) return result;
else result[0] = low;
high = arraySize-1;
while(low<high){
int mid = (low+high)/2 + 1;
if(target<givenArray[mid])
high = mid-1;
else
low = mid;
}
result[1] = high;
return result;
}
};
Solution in Python
def searchRange(self, nums, target):
def binarySearchLeft(givenArray, givenTarget):
left, right = 0, len(A) - 1
while left <= right:
mid = (left + right) / 2
if givenTarget > givenArray[mid]: left = mid + 1
else: right = mid - 1
return left
def binarySearchRight(givenArray, givenTarget):
left, right = 0, len(givenArray) - 1
while left <= right:
mid = (left + right) / 2
if givenTarget >= givenArray[mid]: left = mid + 1
else: right = mid - 1
return right
left, right = binarySearchLeft(nums, target), binarySearchRight(nums, target)
return (left, right) if left <= right else [-1, -1]
Space Time Complexity
Time Complexity: O(log n)
Space Complexity: O(1) since we are only storing two values in our array.
Wrap Up
If you liked the answer for Find First And Last Position of Element in Sorted Array then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.
Wanna read more interview-related questions? Check Top Interview Questions category.
