Formatted question description: https://leetcode.ca/all/34.html
34. 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
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return
Input: nums = [5,7,7,8,8,10], target = 8
Input: nums = [5,7,7,8,8,10], target = 6
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
If the given
target is not in the array, return
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.