34. Find First and Last Position of Element in Sorted Array (Solution || Leetcode medium || Java)

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

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]

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

SOLUTION:

class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ans = {-1,-1};//if not found target returning -1;

//determining range for binary search
int start = 0;
int end = nums.length — 1;

while(start <= end){//Applying binary search
int mid = start + (end — start)/2;

if(nums[mid] == target){
//if target found search for first and last index
ans[0] = search(nums,target,true);
ans[1] = search(nums,target,false);
break;
}
else if(nums[mid] > target){
end = mid — 1;
}
else{
start = mid + 1;
}
}

return ans;
}

//you have to just copy paste binary search, with a little change that is if you want to find the first index change end to mid — 1 or if you want to search for the last index change start to mid + 1

public int search(int[] nums, int target, boolean first){
int ans = -1;
int start = 0;
int end = nums.length — 1;

while(start <= end){
int mid = start + (end — start)/2;

if(nums[mid] == target ){
ans = mid;//storing value of potential answer
if(first){//if searching first index
end = mid — 1;
}else{
start = mid + 1;//if searching last index
}
}
else if(nums[mid] > target){
end = mid — 1;
}
else{
start = mid + 1;
}
}
return ans;//returning index
}
}

PRO TIP:- Write the nums[mid] == target condition as the first condition in if-else statement, anotherwise the code may give “time limit exceeded”

TIME COMPLEXITY :- O(log(n))

SPACE COMPLEXITY :- O(1)

Thank you for reading. If you have any queries, please let me know in the comments section, I will definitely response toward that.