C++ Solution without finding the smallest element


  • 0
    S
    class Solution {
        
    public:
        int binSer(vector<int>& nums, int start, int end, int ind /*Previous Mid element*/, int target, int isleft)
        {
            int mid = (start+end)/2;
            if(nums[mid] == target)
                return mid;
            if(start >= end)
                return -1;
    
            //If right part search
            if(isleft == 0)
            {
                //if in the right search the current mid element is less than the previous mid element
                //Not a normal case in simple binary search
                if(nums[mid] < ind )
                {
                    //compare with target
                    //Prev value||Current value || Direction
                    //Large     ||Large         || Left
                    //Small     ||Small         || Left
                    //Small     ||Large         || Right
    
                    //Fir the 3rd case going to right half
                    if(target < ind && target > nums[mid])
                        return binSer(nums, mid+1, end, nums[mid],target, 0);
                        
                    //For the other 2 cases going to left
                    else
                        return binSer(nums, start, mid-1, nums[mid],target, 1);                
                }
                else
                {
                    //Go to right if current mid element is less than target or
                    //The target lies in between prev and current mid element... 
                    if(nums[mid] < target || (ind > target && nums[mid] > target ))
                        return binSer(nums, mid+1, end, nums[mid],target, 0);
                    //else go to left
                    else
                        return binSer(nums, start, mid-1, nums[mid],target, 1);
                        
                }
            }
            //If left part search
            else
            {
                //if in the left search the current mid element is greater than the previous mid element
                //Not a normal case in simple binary search
                if(nums[mid] > ind )
                {
                   //compare with target
                    //Prev value||Current value || Direction
                    //Large     ||Large         || Right
                    //Small     ||Small         || Right
                    //Large     ||Small         || Left
    
                    //Fir the 3rd case going to left half
                    if(target > ind && target < nums[mid])
                        return binSer(nums, start, mid-1, nums[mid],target, 1);    
                    //Else go to right half        
                    else
                        return binSer(nums, mid+1, end, nums[mid],target, 0);
                }
                else
                {
                    //Go to left if current mid element is greater than target or
                    //The target is greater than previous or current mid element... 
                    if(nums[mid] > target || (ind < target && nums[mid] < target ))
                        return binSer(nums, start, mid-1, nums[mid],target, 1);
                    else
                        return binSer(nums, mid+1, end, nums[mid],target, 0);
                }             
            }
       }
    
    public:
        int search(vector<int>& nums, int target) {
            
            int len = nums.size(), ind;
            if(nums[len/2] == target)
                return len/2;
            
            else 
            {
                return max(binSer(nums, 0, (len/2) - 1, nums[len/2], target, 1) , binSer(nums, (len/2) + 1, len-1, nums[len/2], target, 0));
            }
        }
    };
    

Log in to reply
 

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