binary search, beat 100%


  • 0
    Z
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int left = 0,right = nums.size()-1,mid;
            bool flag = false;
            while(nums[left] > nums[right])
            {
                mid = (left + right) / 2;
                if(nums[mid] > nums[right]) {left = mid + 1;flag = false;}
                else {right = mid - 1;flag = true;}
            }
        
            if(flag) right = right + 1;
            else right = left;
          
            int pos1 = binarySearch(nums,0,right-1,target);
            int pos2 = binarySearch(nums,right,nums.size()-1,target);
            if(pos1 != -1) return pos1;
            if(pos2 != -1) return pos2;
            return -1;
        }
    private:
        int binarySearch(vector<int> & nums,int left,int right,int target)
        {
            while(left <= right)
            {
                int mid = (left + right) / 2;
                if(nums[mid] == target) return mid;
                else if(nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            }
            return -1;
        }
    };

Log in to reply
 

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