Sharing my c_code and 0ms solution, using heap and binary search


  • 0
    L

    as we don't know where the breakpoint of the sorted array is, we can't use binary search. So, at first, we find where nums[j] < nums[j-1], then array nums[0, j) and nums[j, size] are sorted seperatedly, and we can use binary search partitionally;

    How to find the minimum element's index? using the function findMin below which shares the same method as 153. Find Minimum in Rotated Sorted Array

    int findMin(int* nums, int numsSize)
    {
        int i = 0;
        int left;
        int right;
        while(i < numsSize / 2)
        {
            left = 2 * i + 1;
            right = 2 * i + 2;
            if(left < numsSize && nums[i] >= nums[left])
                return left;
            if(right < numsSize && nums[i] >= nums[right])
                return right;
            i++;
        }
        return 0;
    }
    
    int BiSearch(int* nums, int low, int high, int target)
    {
        while(low < high)
        {
            int mid = (low + high) / 2;
            if(target == nums[mid])
                return mid;
            else if(target < nums[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        if(nums[low] == target)
            return low;
        else
            return -1;
    }
    
    int search(int* nums, int numsSize, int target) {
        if(!nums || numsSize <= 0)
            return -1;
        int mid_index = findMin(nums, numsSize);
        if(target == nums[numsSize-1])
            return numsSize-1;
        else if(target < nums[numsSize-1])
            return BiSearch(nums, mid_index, numsSize-2, target);
        else
            return BiSearch(nums, 0, mid_index-1, target);
    }
    

Log in to reply
 

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