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.
nums = [5,7,7,8,8,10], target = 8[3,4]nums = [5,7,7,8,8,10], target = 6[-1,-1]nums = [1], target = 1[0,0]bound=mid then continue left hi=mid−1nums[mid] < target → lo=mid+1 | nums[mid] > target → hi=mid−1bound=mid then continue right lo=mid+1[first, last]. Both are -1 if target not found.A single binary search stops as soon as it finds the target — but there may be duplicates. By not stopping on the first match and instead recording the index and shrinking the search window toward the boundary, each search converges on the extreme position. Two passes of O(log n) remain O(log n) overall.
Finding one 8 and then walking left and right is O(n) if there are many copies. Two binary searches keep it logarithmic.
Run binary search twice. To find the first index, when you hit the target, record it and keep searching left. To find the last index, record it and keep searching right.
On a match, record it and keep searching toward the boundary you want. Two binary searches give the first and the last position.
Run the animation above on your own input, or watch the 1:28 video explanation of Find First and Last Position of Element with a dry run and Java code.