# Question

Formatted question description: https://leetcode.ca/all/34.html

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

Medium

## Description

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]

## Solution

Since the runtime complexity is restricted to be in the order of O(log n), and the array is sorted, binary search is an ideal solution.

Do binary search two rounds. The first round finds whether the given target is in the array nums, and if target exists, get the index of target (if there are duplicates, find any index that has the number target).

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

If the given target is in the array, do binary search for the second round. Do binary search at both sides of the index found in the first round, and find the leftmost index and the rightmost index of target. In the second round, the loop condition of binary search is that the left pointer is less than the right poiner and the equal case is not included in the loop condition, which is a little different from traditional binary search.

Java