Tag Archives: Java

Find first and last position of element in sorted array.

Given a sorted array which contains duplicate elements. Write a code to find first and last position of a number in a sorted array.

OR

Find first and last occurrences of x in sorted array where x is a target value.

If a number is not found return -1.

For example –

Example 1 –

Input : {1, 4, 7, 8, 8, 11, 11, 11, 11, 12, 13, 13} , target = 11

Output: {5, 8}

The first index of 11 is 5 and last index is 8.

Example 2 –

Input: {1, 6, 7, 7, 8, 8, 9, 9},  target = 5

    Output: {-1, -1}

    The target value is not found.

NOTE – We have to solve this problem in O(logn) time complexity.

→