[Algorithms] 3 - Find First and Last Position of Element in Sorted Array

Link to the problem

1. Understanding

Input:

• An array of integers
• Target value

Output:

• An array of two integers (range)

Restriction:

• Need to achieve O(logn) time complexity
• The target is not unique. There can be more than two elements match with the given target value. That is why we are returning an array of the range.

2. Matching

• Sorted array & O(logn): Suggest that we need to use the binary search.

3. Planning

• Find the element has the same value as the target by performing a binary search.

• Now we need to find the starting point and ending point in case there are more than two corresponding target values in the array.

• Two more binary search would be needed to find the starting point (0...mid-1) and the ending point (mid+1...length) because if we perform linear search to find the starting point and the ending point, the time complexity of the algorithm would end up being O(n)