# 34. Find First and Last Position of Element in Sorted Array (Medium)

https://leetcode.com/problems/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 of O(log n).

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

## Solutions

``````class Solution {

// Firstly, binary search the nums and find out one slot of equal value to target
// Next, traverse both sides from above found slot.
// Finally, work out the range of the target value

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

if (nums == null || nums.length == 0) {
return ans;
}

int len = nums.length;

if (target < nums[0] || target > nums[len - 1]) {
return ans;
}

int start = -1;
int end = nums.length - 1;

int mid = binarySearch(nums, target);
if (mid < 0) {
return ans;
}

int left = mid - 1;
while (left >= 0 && nums[left] == target) {
left--;
}

int right = mid + 1;
while (right < len && nums[right] == target) {
right++;
}

return new int[]{left + 1, right - 1};
}

public int binarySearch(int[] nums, int target) {
int left = 0;
int high = nums.length - 1;

// [5,7,7,8,8,10] left=0, right=5, mid=2; left=3,right=5,mid=4, return.
// [5,7,7,8,9,10] left=0, right=5, mid=2; left=3,right=5,mid=4; left=3,right=3,mid=3, return.
while (left <= high) {
int mid = (left + high) / 2;

if (nums[mid] == target) {
return mid;
}

if (nums[mid] < target) {
left = mid + 1;
} else {
high = mid - 1;
}
}

return -1;
}
}
``````