LeetCode刷题——算法学习计划（入门部分）

文章目录

• 题目描述
• 思路介绍
• 我的第一次正确提交
• 官方版本

题目描述

思路介绍

由于本人学算法只是为了巩固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 = 2^m ，即查找次数m=log₂n，省略底数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;
}

同样的代码，怎么运行时间和内存消耗都不一样呢。

官方版本

下面是官方版本

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

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) (指数阶)，的确是不满足题目要求。

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

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，则返回插入位置
}