每日一题#3——二分运算

文章寄语

其实美丽的故事都是没有结局的，只因为它没有结局所以才会美丽。
　　　　　　　　　　　　　　　　　　　　——《萤火之森》

引言

每日一题的记录点.

题目描述

今天的力扣题为 35.搜索插入位置，题目如下：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

立马想出二分查找法。再看看题目范围和提示：无重复元素升序排列数组.

方法和思路

方法一：内置函数

在C#中，有很多可以排序的数据类型，这里仅仅只需要使用列表就足够了。而且这道题无非就是两个子问题：

如果原有数组中存在该数，则返回其索引。
如果原有数组中不存在该数，则返回其应该被插入的位置。

所以我们先把这个数组转换成列表，查找有无该数。如果没有，就把它放到列表里，然后排序后输出索引。

因为我们把它转换成了一个新的数据类型列表，所以占用了n位列表的空间，空间复杂度是O(n)。

public int SearchInsert(int[] nums, int target)
{
    //数组转列表
    List<int> sorted = nums.ToList();
    //如果存在就返回索引 indexof时返回索引的函数
    if (sorted.Contains(target))
        return sorted.IndexOf(target);
    else
    {
        //不存在就加入 排序并输出最后的索引
        sorted.Add(target);
        //因为内置排序函数用了快速排序，所以时间复杂度是nlogn
        sorted.Sort();
        return sorted.IndexOf(target);
    }
}

通过这种方法得出的结果，耗时 (76ms) 和空间 **(38.13MB)**。

方法二：二分运算

所谓二分运算，就是把东西一分为二.

一般就是先在有序数组的最开始和最末尾设定两个扫描头，然后把左边和右边加起来除以二，也就是取中点。

然后我们判断，如果这个数大于这个中点，说明在右半边，然后我们扔掉左半边不要的，循环反复。反之就扔掉右半边。

只不过有一点不一样，如果数组中不存在这个数，我们需要返回的是不大于这个数的最大的数的索引，这个就是他需要被插入的位置。而不是那个中点mid了

因为这里没有开辟新的类型和新的数组，所以只占用了常数量级空间，空间复杂度是O(1)。

public int SearchInsert(int[] nums, int target)
{
    //在开头和结尾定义扫描头
    int left = 0;
    int right = nums.Length - 1;
    //设定约束条件
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        //如果这个数字在数组中存在就返回他的索引
        if (target == nums[mid])
            return mid;
        //不然就按照二分模板，在左边扔掉右边，在右边扔掉左边
        else if (target <= nums[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    //如果这个数字在数组中不存在就返回他的插入位置靠左的索引
    return left;
}

前面提到的[left+(right-left)/2]，这是一种防止溢出的手段，如果数字太大，加起来可能会爆int的范围，所以就这么写。这么写和[(left+right)/2]相同。~~具体什么原理我也不太清楚。~~

通过这种方法得出的结果，耗时 (84ms) 和空间 **(37.59MB)**。

结语和留言

摸鱼摸鱼摸鱼摸鱼摸鱼。

笔记完毕编辑完毕时间CST 10.25 23:26

最后修改于8.15 00:05

蝠池茶园