leetcode-剑指53-I

language: C

与主站34 基本一样
address

// 先用二分法找到第一个，如果找不到，返回0个，找得到，再以此为起点左右计算数量
int search(int* nums, int numsSize, int target){
    int low = 0,high = numsSize-1, count = 0,mid;

    while(low<=high){
        mid =(low +high)/2;
        if(nums[mid]==target){
            count++;
            break;
        }else if(nums[mid]>target){
            high = mid-1;
        }else{
            low = mid +1;
        }
    }
    if(count == 0)
        return 0;
    low = mid+1;  //
    mid--;
    while((mid>=0)&&(nums[mid]==target)){
        count++;
        mid--;
    }
    while((low<numsSize)&&(nums[low]==target)){
        count++;
        low++;
    }
    return count;
}

// 主站34的代码
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    returnSize[0] = 2;
    int *ans = (int *) malloc(sizeof(int)*2);
    int low = 0,high = numsSize-1, count = 0,mid;

    while(low<=high){
        mid =(low +high)/2;
        if(nums[mid]==target){
            count++;
            break;
        }else if(nums[mid]>target){
            high = mid-1;
        }else{
            low = mid +1;
        }
    }
    if(count == 0){
        ans[0] = -1;
        ans[1] =-1;
        return ans;
    }
    low = mid+1;  //
    mid--;
    while((mid>=0)&&(nums[mid]==target)){
        mid--;
    }
    ans[0] = mid +1;
    while((low<numsSize)&&(nums[low]==target)){
        low++;
    }
    ans[1] = low-1;
    return ans;
}