C iterative O(log n) binary search solution


  • 0
    R
    #define NOT_FOUND -1
    
    int search(int* nums, int numsSize, int target) {
        
        int left = 0;
        int right = numsSize - 1;
        int mid = 0;
            
        while(left <= right)
        {
            mid = left + (right - left) / 2;
            
            // if mid index is the target, return the index
            if(nums[mid] == target)
            {
                return mid;
            }
            
            // if not, then if mid is in the rotated section/larger 
            // numbers subsection i.e. mid will be greater than both ends
            else if(nums[mid] >= nums[right] && nums[mid] >= nums[left])
            {
                if(target > nums[mid])
                {
                    left = mid + 1;
                }
                
                else if(target <= nums[right])
                {
                    left = mid + 1;
                }
                
                else if(target > nums[right])
                {
                    right = mid - 1;
                }
            }
            
            // if not, then if mid is in the smaller numbers subsection i.e. 
            // mid will be lesser than both ends in the array
            else
            {
                if(target < nums[mid])
                {
                    right = mid - 1;
                }
                
                else if(target > nums[right])
                {
                    right = mid - 1;
                }
                
                else if(target <= nums[right])
                {
                    left = mid + 1;
                }
            }
        }
        
        return NOT_FOUND;
    }
    

Log in to reply
 

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