> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/medium/34.-find-first-and-last-position-of-element-in-sorted-array.md).

# 34. Find First and Last Position of Element in Sorted Array

## Intuition

Since the array is **sorted**, we can use **binary search** to find:

1. The **first occurrence** of the target.
2. The **last occurrence** of the target.

Instead of expanding linearly after finding the target (which can take O(n) in worst case), we can use two separate binary search calls to maintain the required **O(log n)** time complexity.

## Complexity

| Space Complexity | Time Complexity       |
| ---------------- | --------------------- |
| $$\text{O}(1)$$  | $$\text{O}(\log{N})$$ |

## Code

```java
// Binary search to find the first (leftmost) occurrence
private int findFirst(int[] nums, int target) {
    int left = 0, right = nums.length - 1, first = -1;

    while (left <= right) {
        int mid = (left + right) >> 1;

        if (nums[mid] == target) {
            first = mid;         // potential answer found
            right = mid - 1;     // keep looking on the left
        } else if (nums[mid] < target) {
            left = mid + 1;      // move right
        } else {
            right = mid - 1;     // move left
        }
    }

    return first;
}

// Binary search to find the last (rightmost) occurrence
private int findLast(int[] nums, int target) {
    int left = 0, right = nums.length - 1, last = -1;

    while (left <= right) {
        int mid = (left + right) >> 1;

        if (nums[mid] == target) {
            last = mid;         // potential answer found
            left = mid + 1;     // keep looking on the right
        } else if (nums[mid] < target) {
            left = mid + 1;     // move right
        } else {
            right = mid - 1;    // move left
        }
    }

    return last;
}

// Main function
public int[] searchRange(int[] nums, int target) {
    int firstIndex = findFirst(nums, target);
    int lastIndex = findLast(nums, target);
    return new int[]{firstIndex, lastIndex};
}
```