# Search for a Range (Find First and Last Position of Element in Sorted Array)

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

Your algorithm's runtime complexity must be in the order ofO(logn).

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

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]
``````

## Analysis

``````if (target <= nums[mid]) {
right = mid;
} else {
left = mid;
}
``````

``````if (target >= nums[mid]) {
left = mid;
} else {
right = mid;
}
``````

## Solution

Using Template #3 - Two Binary Searches (6 ms, 33.53%)

``````class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[] {-1, -1};
if (nums == null || nums.length == 0) return res;

int left, right;

// Binary Search 1 - Left Boundary
left = 0;
right = nums.length - 1;

while (left + 1 < right) {
int mid = left + (right - left) / 2;

if (target <= nums[mid]) {
right = mid;
} else {
left = mid;
}
}

if (nums[left] == target) {
res[0] = left;
} else if (nums[right] == target) {
res[0] = right;
}

// Binary Search 2 - Right Boundary
left = 0;
right = nums.length - 1;

while (left + 1 < right) {
int mid = left + (right - left) / 2;

if (target >= nums[mid]) {
left = mid;
} else {
right = mid;
}
}

if (nums[right] == target) {
res[1] = right;
} else if (nums[left] == target) {
res[1] = left;
}

return res;
}
}
``````

Combined two binary searches In Helper function - (6ms 33.53%)

``````class Solution {
// returns leftmost (or rightmost) index in `nums` for `target` via binary search.
private int extremeInsertionIndex(int[] nums, int target, boolean leftMost) {
if (nums == null || nums.length == 0) return -1;
int lo = 0;
int hi = nums.length - 1;

while (lo + 1< hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > target || (leftMost && target == nums[mid])) {
hi = mid;
}
else {
lo = mid;
}
}
if (leftMost) {
if (nums[lo] == target) {
return lo;
} else if (nums[hi] == target){
return hi;
}
} else {
if (nums[hi] == target) {
return hi;
} else if (nums[lo] == target){
return lo;
}
}
return -1;
}

public int[] searchRange(int[] nums, int target) {
int[] targetRange = {-1, -1};

int leftIdx = extremeInsertionIndex(nums, target, true);
int rightIdx =  extremeInsertionIndex(nums, target, false);

targetRange[0] = leftIdx;
targetRange[1] = rightIdx;

return targetRange;
}
}
``````