> 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/coding_practice_questions/interview_questions_4/search-in-rotated-array.md).

# Search in Rotated Array

**10.3 Search in Rotated Array:** Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order.

```
EXAMPLE
Input:find 5 in { 15, 16, 19, 20, 25, 1, 3, 4, 5, 7,10, 14 }
Output: 8 (the index of 5 in the array)
```

* O(logN) time, with O(N) extra space (recursive)
* Algorithm: Find focal point in logn (minimum), preform binary search of left or right half.

```cpp
// finding min element in O(logN)
int find_focal(vector<int> &ar, int low, int high) {
    // not rotated
    if (ar.begin()[1] < ar.end()[-1]) return 0;
    else {
        int middle = low + ((high - low) / 2);

        // min element = next element is smaller || prev element is larger
        if (ar.at(middle + 1) < ar.at(middle))
            return middle + 1;
        if (ar.at(middle - 1) > ar.at(middle))
            return middle;

        // search right
        else if (ar.at(low) < ar.at(middle)) {
            find_focal(ar, middle + 1, high);
        }
        else {
            find_focal(ar, low, middle - 1);
        }
    }
}

int binary_search(vector<int> &ar, int low, int high, int target) {
    if (high < low) return INT_MIN;

    int middle = low + ((high - low) / 2);

    if (ar.at(middle) == target) return middle;
    // search right
    else if (ar.at(middle) < target) {
        binary_search(ar, middle + 1, high, target);
    }
    else {
        binary_search(ar, low, middle - 1, target);
    }

}


int find_rotated(vector<int> &ar, int findthis) {
    if (ar.empty()) return INT_MIN;

    // 1) Find focal point (min element)
    int focal = find_focal(ar, 0, ar.size() - 1);
    if (ar.at(focal) == findthis) return focal;

    // search right
    if (findthis > ar.at(focal) && findthis <= ar.end()[-1]) {
        return binary_search(ar, focal + 1, ar.size() - 1, findthis);
    }
    // search left
    else {
        return binary_search(ar, 0, focal - 1, findthis);
    }
}



int main() {
    vector<int> ar = { 15, 16, 19, 20, 25, 1, 3, 4, 5, 7,10, 14 };
    cout << find_rotated(ar, 5) << endl;

    ar = { 20, 25, 1, 3, 4, 5, 7,10, 14, 15, 16, 17, 18 };
    cout << find_rotated(ar, 5) << endl;
}
```


---

# 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/coding_practice_questions/interview_questions_4/search-in-rotated-array.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.