Algorithm to find minimum in array of point

user_13100783 0
Viewed 140

I have a vector of values with the minimum, but which is non-decreasing after it and non-increasing before. Here is the example:

std::vector<int> arr = {90, 80, 70, 60, 55, 62, 71, 89, 104}

In the example I want to find 55. I want to be able to find its minimum efficiently. O(n) complexity is not enough. Supposedely, it is possible to some sort of modify binary search, but I would like to know whether there are existing solutions.

search algorithm c++
1 Answers

You can achieve O(lg n) complexity as follows:

int findTurningPoint(const vector<int>& v, int begin, int end) {
    int mid = (begin + end) / 2;
    if (v[mid - 1] > v[mid] && v[mid + 1] > v[mid]) {
        return mid;
    } else if (v[mid - 1] > v[mid]) {
        return findTurningPoint(v, mid + 1, end);
    } else if (v[mid - 1] < v[mid]) {
        return findTurningPoint(v, begin, mid - 1);
    }
}

vector<int> arr = {90, 80, 70, 60, 55, 62, 71, 89, 104};
cout << findTurningPoint(arr, 0, arr.size() - 1); // 4

Method explained:

Select the element in the middle of the vector. Check whether it forms a minima by comparing it with its neighbours. If not, find whether this element and its neighbours form an increasing sequence. If they do, repeat the above process for all elements to the left of the middle element. Otherwise, repeat the process for all elements to the right of the middle element.

user_66497860
Related