java Single Binary Search Solution


  • 0
    V

    In this problem , complexity is to move to which side of the array, which is decided by
    the sequence type of numbers at index low,mid and high.

    Sequence type 1 => big numbers on both left and right
    Sequence type 2 => small on left and big on right
    Sequence type 3 => small numbers on both left and right
    Sequence type 4 is low = mid and mid = high , so hence I returned -1 for it.

    public class Solution {
        
        public int sequenceType(int x,int y,int z)
        {
            if(x >= y && z > y )
                return 1;
            if(x <= y && y < z)
                return 2;
            if(x <= y && z < y)
                return 3;
            
            return -1;
        }
        public int search(int[] nums, int target) {
            
            int low = 0,
                mid = 0,
                high = nums.length - 1;
                 
            
                
            while(low <= high)
            {
                mid = low + (high - low) / 2;
                
                
                if(nums[mid] == target)
                    return mid;
    
                switch(sequenceType(nums[low],nums[mid],nums[high]))
                {
                    case 1:
                        if(nums[mid] < target && target <= nums[high])
                            low = mid + 1;
                        else
                            high = mid - 1;
                    break;
                    case 2:
                    case 3:
                        if(nums[low] <= target && target < nums[mid])
                            high = mid - 1;
                        else
                            low = mid + 1;
                    break;
                    default:
                        return -1;
                }
            }
            
            
            
            return -1;
        }
    }
    

Log in to reply
 

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