# C++ version, easy to understand

• ``````/*
二分 分情况讨论
4种情况，升序，降序，山谷，山峰
*/

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

int binarySearch(vector<int> &nums, int lo, int hi, int target) {
if (lo > hi) return -1;
int mid = lo+(hi-lo)/2;
if (nums[mid] == target) return mid;
if (nums[mid] >= nums[lo] && nums[mid] <= nums[hi]) {
if (target > nums[mid]) return binarySearch(nums, mid+1, hi, target);
else return binarySearch(nums, lo, mid-1, target);
} else if (nums[mid] <= nums[lo] && nums[mid] >= nums[hi]) {
if (target > nums[mid]) return binarySearch(nums, lo, mid-1, target);
else return binarySearch(nums, mid+1, hi, target);
} else if (nums[mid] <= nums[lo] && nums[mid] <= nums[hi]) {
if (target > nums[mid] && target <= nums[hi]) return binarySearch(nums, mid+1, hi, target);
else return binarySearch(nums, lo, mid-1, target);
} else {
if (target > nums[mid] || target <= nums[hi]) return binarySearch(nums, mid+1, hi, target);
else return binarySearch(nums, lo, mid-1, target);
}
}
};

/* force binary search*/
class Solution {
public:
int search(vector<int>& nums, int target) {
return binarySearch(nums, 0, nums.size()-1, target);
}
int binarySearch(vector<int> &nums, int lo, int hi, int target) {
if (lo > hi) return -1;
int mid = lo+(hi-lo)/2;
if (nums[mid] == target) return mid;
int left = binarySearch(nums, lo, mid-1, target);
return left == -1 ? binarySearch(nums, mid+1, hi, target) : left;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.