C++ version, easy to understand


  • 0
    T
    /*
    二分 分情况讨论
    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;
        }
    };

Log in to reply
 

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