每日计划

7/4/2022 MON

• 704、二分查找
• 35、搜索插入位置
• 34、在排序数组中查找元素的第一个和最后一个位置
• 69、x的平方根
• 367、有效的完全平方数

 704、二分查找

第一次提交结果：超出时间限制。

int search(int* nums, int numsSize, int target){
    int left=0;
    int right=numsSize;
    while(left<right)
    {
        int middle=left+((right-left)/2);
        if(nums[middle]>target)
        {
            right=middle;
        }
        else if(nums[middle]<target)
        {
            left=middle;
        }
        else
        {
            return middle;
        }
    }
    return -1;
}

第二次提交结果：通过

int search(int* nums, int numsSize, int target){
    int left=0;
    int right=numsSize-1;
    while(left<=right)
    {
        int middle=(left+right)/2;
        if(nums[middle]>target)
        {
            right=middle-1;
        }
        else if(nums[middle]<target)
        {
            left=middle+1;
        }
        else
        {
            return middle;
        }
    }
    return -1;

错误原因：

二分查找涉及边界条件。

while(left<right) or while(left<=right)，right=middle or right=middle-1。

区间的定义就是不变量。

写二分法，区间定义一般为两种，左闭右闭[left,right]，左闭右开[left,right)。

题中描述：

1. n 将在 [1, 10000]之间。
2. nums 的每个元素都将在 [-9999, 9999]之间。

所以该二分查找应该采用左闭右闭的写法而不是第一次提交的左闭右开的写法。

35、搜索插入位置 

第一次提交结果：可以完成位置查找，无法完成插入。显示超出限制时间。

int searchInsert(int* nums, int numsSize, int target){
    int left=0;
    int right=numsSize;
    while(left<right)
    {
        int middle=(right+left)/2;
        if(target==nums[middle])
        {
            return middle;
        }
        else
        {
            if(nums[middle]>target)
            {
            right=middle;
            }
            else if(nums[middle]<target)
            {
            left=middle;
            }
        }
    }
    int i;
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]>target&&nums[numsSize-1]>target)
        {
            return i;
        }
        else if(nums[numsSize-1]<target)
        {
            return numsSize;
        }
    }
    return 0;
}

第二次提交结果：通过

int searchInsert(int* nums, int numsSize, int target){
    int left=0;
    int right=numsSize-1;
    while(left<=right)
    {
        int middle=(left+right)/2;
        if(nums[middle]>target)
        {
            right=middle-1;
        }
        else if(nums[middle]<target)
        {
            left=middle+1;
        }
        else
        {
            return middle;
        }
    }
    return right+1;
}

原因：

遇到有序无重复数组考虑二分法

由于题目给的target是左闭右闭，所以应该使用 right=numsSize-1; while(left<=right); right=middle-1.

若区间定义为左闭右开 则right=numsSize; while(left<right); right=middle.

当数组中没有查找的数字时，直接返回一个数right+1就可以表示需要插入的位置，不需要繁琐地判断。

34、 在排序数组中查找元素的第一个和最后一个位置

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int* result=(int*)malloc(sizeof(int)*2);
    result[0]=-1;
    result[1]=-1;
    int left=0;
    int right=numsSize-1;
    while(left<=right)
    {
        int middle=(left+right)/2;
        if(nums[middle]>target)
        {
            right=middle-1;
        }
        else if(nums[middle]<target)
        {
            left=middle+1;
        }
        else//nums[middle]==target
        {
            left=middle;
            right=middle;
            while(left>0&&nums[left]==nums[left-1])
            {
                left--;
            }
            while(right<numsSize-1&&nums[right]==nums[right+1])
            {
                right++;
            }
            result[0]=left;
            result[1]=right;
            *returnSize=2;
            return result;
        }
    }
    return result;
}

69、x的平方根

求算术平方根就是用这个数除一个数，看是不是等于这个数。分大小于情况可以二分法 

int mySqrt(int x){
    if(x==0)
    return 0;
    int left=1,right=x;
    while(left<=right)
    {
        int mid=left+(right-left)/2;
        if(mid>x/mid)
        {
            right=mid-1;
        }
        else if(mid<x/mid)
        {
            left=mid+1;
        }
        else
        {
            return mid;
        }
    }
    return right;
}

367、有效的完全平方数

/*错误。无法判断5是不是完全平方数*/
bool isPerfectSquare(int num){
    int left=1;
    int right=num;
    while(left<=right)
    {
        int mid=left+(right-left)/2;
        if(mid>num/mid)
        {
            right=mid-1;
        }
        else if(mid<num/mid)
        {
            left=mid+1;
        }
        else
        {
            if(num%mid==0)
                return true;
        }
    }
    return false;
}

/*把返回true的放在前面就可以了，为什么*/
bool isPerfectSquare(int num){
    int left=1;
    int right=num;
    while(left<=right)
    {
        int mid=left+(right-left)/2;
        if(num/mid==mid&&num%mid==0)
        {
            return true;
        }
        else if(mid>num/mid)
        {
            right=mid-1;
        }
        else
        {
            left=mid+1;
        }
    }
    return false;
}