# 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: 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:

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

The question should be specific, self-contained, and written in natural language.
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.