算法入门C——35. 搜索插入位置

LeetCode刷题——算法学习计划(入门部分)

文章目录

题目描述

算法入门C——35. 搜索插入位置

思路介绍

由于本人学算法只是为了巩固C语言基础,所以就不会去深挖算法之根本

算法:二分法查找适用于数据量较大时,但是数据需要先排好顺序。主要思想是:(设查找的数组区间为array[low, high])
(1)确定该区间的中间位置K(2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。区域确定如下:a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……,K-1]b.array[k]<T 类似上面查找区间为array[k+1,……,high]。每一次查找与中间值比较,可以确定是否查找成功,不成功当前查找区间将缩小一半,递归查找即可。时间复杂度为:O(log2n)。——百度百科

若算法的T(n) =O(logn),则称其具有对数时间。由于计算机使用二进制的记数系统,对数常常以2为底(即log2n,有时写作lgn)。然而,由对数的换底公式,logan和logbn只有一个常数因子不同,这个因子在大O记法中被丢弃。因此记作O(logn),而不论对数的底是多少,是对数时间算法的标准记法。
常见的具有对数时间的算法有二叉树的相关操作和二分搜索。
对数时间的算法是非常有效的,因为每增加一个输入,其所需要的额外计算时间会变小。
递归地将字符串砍半并且输出是这个类别函数的一个简单例子。它需要O(log n)的时间因为每次输出之前我们都将字符串砍半。 这意味着,如果我们想增加输出的次数,我们需要将字符串长度加倍。——百度百科

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)
二分法的时间复杂度为O(logn),这个logn怎么来的呢?

我们使用二分查找时,每次查找都会将剩下的内容一分为二,第一次为1/2,第二次1/4,第m次为(1/2)m,直到最后只剩一个查找对象(最坏情况),也就是1。假如一共有n个对象,查找m次,就可以得出公式:n(1/2) m = 1 ,简单换算得到 n = 2m ,即查找次数m=log2n,省略底数2,即得出m=logn,所以二分查找的时间复杂度为O(logn)。

我的第一次正确提交

由于昨天已经练过二分查找,所以这题也没遇到太大麻烦,但和标准答案比,我还是有优化空间的。

int searchInsert(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(target == nums[mid])
            return mid;
        else if(target > nums[mid])
            left = mid + 1;
        else 
            right = mid - 1;
    }
    if(target < nums[mid]) //这个if可以合到while循环中去,参考官方版本(下文)
        return mid;
    else 
        return mid + 1;
}

同样的代码,怎么运行时间和内存消耗都不一样呢。
算法入门C——35. 搜索插入位置

官方版本

下面是官方版本

看来我永远都不能达到这种高度了,每次都比官方代码低一个档次。

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

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/search-insert-position/solution/sou-suo-cha-ru-wei-zhi-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


虽然题目要求了时间复杂度要为O(logn),但我还是用了一个土方法提交

int searchInsert(int* nums, int numsSize, int target)
{
    int i = 0;

    if(target > nums[numsSize - 1])
        return numsSize;
    for(i = 0; i < numsSize; i++)
    {
        if(target <= nums[i])
            return i;  
    }
    return 0;
}

用这种方法,如果数组有n个数,最坏情况要找m次,那么m和n就满足m=1*n,即时间复杂度为O(n),根据O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶),的确是不满足题目要求。

算法入门C——35. 搜索插入位置


错误记录:没考虑小于数组最小值的情况。

算法入门C——35. 搜索插入位置

int searchInsert(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(target == nums[mid])
            return mid;
        else if(target >= nums[mid])
            left = mid + 1;
        else 
            right = mid - 1;
    }
    return mid + 1; //如果数组中没有target,则返回插入位置
}
上一篇:杨辉三角的简单实现(C++)


下一篇:开发有35岁危机,测试怎么样?