clean C++ solution with explanation


  • 0
    D
    class Solution {
    public:
        bool search(vector<int>& nums, int target) {
            int lo = 0, hi = nums.size() - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (nums[mid] == target) return true;
                else if (nums[mid] > nums[hi]) { // min on right side
                    if (target >= nums[lo] && target < nums[mid]) hi = mid; // target is on left side of mid
                    else lo = mid + 1;
                }
                else if (nums[mid] < nums[hi]) { // min on left side
                    if (target <= nums[hi] && target > nums[mid]) lo = mid + 1; // target is on right side of mid
                    else hi = mid;
                }
                else {  // can't decide position of min and position of target
                    hi--;  
                }
            }
            return false;
        }
    };
    

Log in to reply
 

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