https://leetcode.com/problems/search-in-rotated-sorted-array/

answer.cc

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return nums.empty() ? -1 : find(nums, target, 0, nums.size() - 1);
    }

    int find(const vector<int>& nums, int target, int start, int end) {
        // cout << start << " " << end << endl;
        if (start == end) {
            return nums[start] == target ? start : -1;
        }
        int mid = (start + end) / 2;
        if (nums[start] <= nums[mid]) {
            // The first half of the list is sorted. Check if the target exists
            // in the first half.
            if (nums[start] <= target && target <= nums[mid]) {
                return find(nums, target, start, mid);
            } else {
                return find(nums, target, mid + 1, end);
            }
        } else { // Here, nums[mid + 1] < nums[end].
            // The latter half of the list is sorted. Check if the target exists
            // in the latter half.
            if (nums[mid + 1] <= target && target <= nums[end]) {
                return find(nums, target, mid + 1, end);
            } else {
                return find(nums, target, start, mid);
            }
        }
    }
};