73. Find First and Last Position of an Element in a Sorted Array

Given a sorted array of n integers and a target value, find the first and last index at which the target occurs. Print them as 'first last', or '-1 -1' if the target isn't present.

Input: The first line contains an integer n. The second line contains n space-separated sorted integers. The third line contains the target value. Output: Print 'first last' - the first and last index at which the target occurs, or '-1 -1' if it doesn't occur.

1 <= n <= 10^5

A normal binary search STOPS the moment it finds any match - the key insight here is to keep narrowing the search window even after finding a match, specifically to push toward one particular boundary (leftmost or rightmost).

In a sorted array, find both the first and last index where a target value occurs. Brute force: Scan the array linearly from the front to find the first occurrence, and from the back to find the last - this costs O(n), unnecessary given the array's sorted structure, which allows a much faster binary search. Optimised: Two slightly modified binary searches (one that keeps narrowing left after a match, one that keeps narrowing right) each run in O(log n) - this is far faster than a linear scan, especially valuable when there are many repeated values or many queries.

Scan through the entire array from left to right, recording the index of the first time the target is seen and continually updating the index of the last time it's seen. This trivially works for any array, sorted or not, but it completely ignores the fact that the array is sorted, so it takes linear time even though the target's occurrences are guaranteed to form one contiguous block. Time: O(n) Space: O(1)

Use a standard binary search to quickly land on any one index where the target occurs, then walk left from that index while the value keeps matching to find the first occurrence, and walk right similarly to find the last occurrence. This exploits the sortedness to locate the target in logarithmic time instead of an immediate full scan, though if the target happens to occur a huge number of times the outward expansion can still cost linear time in the worst case. Time: O(log n + k) where k is the number of occurrences Space: O(1)

Run two separate modified binary searches: one that keeps narrowing toward the leftmost index equal to the target (moving the right boundary inward even after finding a match), and one that keeps narrowing toward the rightmost index equal to the target (moving the left boundary inward after a match). Both searches always halve the remaining range regardless of how many times the target repeats, so the total cost stays logarithmic no matter how many duplicates exist, unlike the outward-expansion approach. Time: O(log n) Space: O(1)

1. Run one binary search specifically biased to find the LEFTMOST occurrence: when you find a match, keep searching further LEFT for an even earlier one. 2. Run a second binary search biased to find the RIGHTMOST occurrence: when you find a match, keep searching further RIGHT for an even later one. 3. Combine both results; if the target isn't found at all, print '-1 -1'.

Time: O(log n) - two independent binary searches. Space: O(1) - just a few pointer variables.

Test a target absent from the array ('-1 -1'), a target occurring exactly once (first equals last), and n = 10^5 for performance.

This is one of the most classic 'binary search variant' interview questions - be ready to clearly explain the small but crucial modification (continuing to search after finding a match, rather than stopping immediately) that turns a normal binary search into a boundary-finding one.