> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binarysearch/search-for-a-range.md).

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

https\://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

> Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
>
> Your algorithm's runtime complexity must be in the order of O(log n).
>
> If the target is not found in the array, return \[-1, -1].
>
> For example,
>
> Given \[5, 7, 7, 8, 8, 10] and target value 8,
>
> return \[3, 4].

## Thoughts

两次lower\_bound，第二次用在target +1，无论找没找到最后都会落在target所在最后位置的后一个（如果有）前移一个就是target所在最后位置。

## Code

```
/*
 * @lc app=leetcode id=34 lang=cpp
 *
 * [34] Find First and Last Position of Element in Sorted Array
 */

// @lc code=start
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) return vector<int>{-1, -1};
        const auto lower_bound = [&](int target) {
            int start = 0, end = nums.size() - 1;
            while (start < end) {
                int mid = start + (end - start) / 2;
                if (nums[mid] < target) start = mid + 1;
                else end = mid;
            }
            return start;
        };
        int l = lower_bound(target);
        if (nums[l] != target) return vector<int>{-1, -1};
        int h = lower_bound(target + 1);
        if (nums[h] == target) return vector<int>{l, h};
        return vector<int>{l, h - 1};
    }
};
// @lc code=end


```

```
class Solution {
    private int binSearch(int[] nums, int target) {
        int start = 0, end = nums.length;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        return start;
    }

    // find the first number that is greater than or equal to target.
    // could return A.length if target is greater than A[A.length-1].
    // actually this is the same as lower_bound in C++ STL.
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        int start = binSearch(nums, target);
        if (nums.length == start || nums[start] != target) {
            return res;
        }
        res[0] = start;
        res[1] = binSearch(nums, target + 1) - 1;
        return res;
    }
}
```

## Analysis

复杂度O(lgn)