第一天——二分查找

强烈推荐大佬的文章 点此跳转

题目示例还是蛮长的

所以接下来我都会只放描述并且附上原题目链接


704.二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target

写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

public class Solution {
    public int Search(int[] nums, int target) 
    {
        int start = 0;
        int last = nums.Length-1;
        while(start <= last)
        {
            int mid = (last - start)/2 + start;
            if(target == nums[mid])
            {
                return mid;
            }
            else if(target < nums[mid])
            {
                last = mid - 1;
            }
            else if(target > nums[mid])
            {
                start = mid + 1;
            }
        }
        return -1;
    }
}

我不知道大佬们都是怎么写的

我这个写法应该算蛮标准的二分

但是在C#提交记录里只超过了13%

所以来说说二分法吧

如果是C/C++,通常我们可能会用指针去做这件事

C#虽然不支持指针但毕竟算法思路是一样的

最左就默认0,最右就默认数组长度减一

但是mid的值为什么是(最右-最左)/2 + 最左?

为什么不是(最右+最左)/2?

int是有长度的,两个int相加

假如这个数组的长度非常长,刚好在int的最大值边缘

一相加就直接寄了

搜索区间

当我们发现目标值在mid的左边

此时我们就可以缩小区间为[0,mid)

也就是0到mid-1

所以最右就等于mid-1

同理目标值在mid的右边的话

最左就要等于mid+1

while的循环条件为什么是小于等于?

初始化的时候最右因为是数组,所以取的是长度减一

那么问题来了,什么时候你需要停止搜索呢?

找到了自然不用说,那没找到呢?

肯定是中间没有数可以比了才不用找了

数组可不是指针,索引之间相差一的时候两个数才是相邻的

所以需要小于,但是这两个数也需要比

所以就要考虑到这两个数重合的情况

也就是等于


278.第一个错误的版本

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

提示:

  • 1 <= bad <= n <= 231 - 1
/* The isBadVersion API is defined in the parent class VersionControl.
      bool IsBadVersion(int version); */

public class Solution : VersionControl {

    public int FirstBadVersion(int n) 
    {
        int start = 1;
        int last = n;
        int version = n;

        while(start <= last)
        {
            int mid = (last - start)/2 + start;

            if(IsBadVersion(mid))
            {   
                version = mid;
                last = mid-1;
            }
            else
            {
                start = mid+1;
            }
        }

        return version;
    }

}

因为做第一题的时候没好好复习

这题就在while的小于等于以及mid的溢出出现了问题

这提示就是在告诉你要考虑溢出的情况

万一哪个苦逼产品经理的产品迭代了2的31次方呢

这道题最主要的关键点在于

怎样判断哪个版本是第一个出错的

所以在循环外定义了个version用来记录

如果巧了,mid对应的是错的

那么我们就要在这记录一下version

然后把搜索区间向前

如果很不巧mid对应的不是错的

就得把搜索区间往后

但是不用记录version


35.搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.Length - 1;
        int number = 0;

        while(low <= high)
        {
            int mid = (high - low)/2 + low;
            if(target == nums[mid])
            {
                return mid;
            }
            else if(target < nums[mid])
            {
                high = mid-1;
            }
            else if(target > nums[mid])
            {
                low = mid+1;
                number = low;
            }

            if(number < 0)
            {
                number = 0;
            }
        }

        return number;
    }
}

主要问题在于返回索引

没有目标数它就要返回将要插入的位置的索引

如果相等不用说,直接返回mid

但是其他情况呢?

while的判断条件决定了当while结束的时候

数组总会被划分成两部分

一种情况是left = right

那么肯定返回left的值了

一种情况是right = right +1

此时left正好是right左侧相邻的索引

那么为了不越界所以我们肯定选择left

但是要考虑到在0位插入的情况

所以小于0的数只能插入到第0位

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注