> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/34_search_for_a_range.md).

# 34 Search for a Range

Given a sorted array of integers, 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]
```

* Binary search for the number, then expand our left and right from that index until you reach a different 'target' number. This will give us the range of numbers, but it doesn't run in O(logn). Consider the case when all the numbers in the array are the target number. Then binary search would return the middle index, and then expanding out left and right would run in O(n).

```cpp
int binary_search(vector<int> &nums, int low, int high, int key) {
    if (high < low) return -1;
    int median = low + ((high - low) / 2);
    if (nums.at(median) == key) {
        return median;
    }
    else if (nums.at(median) < key) {
        // search right
        return binary_search(nums, median + 1, high, key);
    }
    else {
        // search left
        return binary_search(nums, low, median - 1, key);
    }
}


vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> range(2);
    // find the number
    int index = binary_search(nums, 0, nums.size() - 1, target);
    if (index == -1) {
        return range = { -1, -1 };
    }
    else {
        // expand right
        int i;
        for (i = index; i < nums.size(); i++) {
            if (nums.at(i) != target) {
                break;
            }
        }

        // expand left
        int j;
        for (j = index; j >= 0; j--) {
            if (nums.at(j) != target) {
                break;
            }
        }
        return range = { j + 1, i - 1 };
    }
}
```

**Improved O(logN) version**

* Simply replace with this function

```cpp
vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> range(2);

    // find the number
    int index = binary_search(nums, 0, nums.size() - 1, target);

    if (index == -1) {
        return range = { -1, -1 };
    }

    // expand left
    int prev_left = index;
    int left = index;
    while (left != -1) {
        prev_left = left;
        left = binary_search(nums, 0, --left, target);
    }
    left = prev_left;

    // expand right
    int prev_right = index;
    int right = index;
    while (right != -1) {
        prev_right = right;
        right = binary_search(nums, ++right, nums.size() - 1, target);
    }
    right = prev_right;

    return range = { left, right };
}
```

* Rather than just expanding left and right linearly, we first find the target with binary search, and then we binary search out right and left directions. The first occurance that the number is not found, means that the index returned by the previous iteration was the edge case, and hence in part of the maximum range.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/34_search_for_a_range.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.