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.

// 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;
}