我在代码随想录算法训练营写代码之704二分查找、27移除元素

第一题?704 二分查找

题目如下:

一刷:

题目思路分析:

我设置了?i?代表区间范围的左边界,设置 j 为区间范围内的右边界,由于一开始我不知道判断我们要查找的值是否在区间内,然后我就设置了mid代表我们要返回的值,然后进入循环去不断去缩小区间,mid 我们的中间值。

为什么要用 mid? = (j-i)/2+i 而不用 mid = (j+i)/2 ?

其实后者可能越界,用?mid? = (j-i)/2+i 可以避免越界的风险,然后就是我们 if 的判断了,当我们的中间位置的值大于我们要找的值target 我们就将我们的左边界 i 向移动到区间中点位置的前一位,当我们的中间位置的值小于我们要找的值target 我们就将我们的右边界 j 向移动到区间中点位置的后一位,如果相等我们直接返回我们的中间值的小标就可以了。然后我们就要判断我们搜索的数组中是否有我们的值了我们用了?if 将值取出然后和?target ?进行比较,如果相同就返回 mid /如果不相同则返回 -1,其实这里是多余的我们直接返回?-1?就可以因为如果可以找到值的话就会在while?循环中返回。?

?为什么我们要每次移动都要将左右点移动到前一位和后一位呢??(问题先放这后面解答)

二刷:

总结了经验: 我发现我的变量命名习惯不是特别好,导致有时候在去想二分的左边界和右边界的时候有点搞不太清楚,因为一般 i 和 j 都用于循环中递增加,然后现在用于表示左右顶点可能有问题所以二刷的时候解决这个问题

这里我们直接返回-1而不用判断,而且我们的命名方式也变得更加直观

三刷:

第三刷的主要目的就是要将而分搜索区间理解下上面的二分理解了套个模版就可以但是区间的理解可以说是比较重要了,一刷和二刷主要用的是左闭右闭,而三刷用的是左闭右开

我们知道二分搜索其实就是将区间缩小,我们操作是区间,那么是区间就有左右开闭之分我们.一般的查找其实是左闭右闭,但是有时候我们并不需要去查找一些区级范围,而且一些区间如果没有处理好可能会出现问题 比如? [1,1) 这个左闭右开是存在问题的,所以我们在定义区间的时候要小心,当我们要规定二分查找的区间是左闭右开的时候,我们就要考虑左右点的范围,我们这里的右顶点不再减一因为我们的区间要包含我们要查找的下标当,我们减一我们我们就会将区间点移动到区间外面,因为我们的区间是左闭右开,上面的问题也是这样我们知道中间值大于或者小于我们要查找的值我们就不用去找中间值我们就要将我们的下标向左或者向右移动

?第二题:27 移除元素

题目:

一刷过:方法双指针

题目思路分析:

这个题目要我们移除元素,但是我们知道我们数组中的元素其实不是真正的删除我们实现的是覆盖,我们定义了一个计数器 cnt 用于计数然后用 for 循环去查找我们的数组中的元素,当我们数组中的元素不是 val 我们就可以将我们可以用记数器进行从开始将元素重新覆盖到原来的vector容器中,这里的?cnt?不仅充当计数器也充当下标 最后我们将我们的统计的值返回就可以了。

?

今日总结:

题目还算简单,写起来快,但是写文章打字,是真的比较慢但是,写完以后确实感觉对题目理解更加通透,明天也要加油了。