备战秋招-嵌入式刷力扣Day1-数组二分查找
·
1.数组是存放在连续内存空间上的相同类型数据的集合。
数组下标都是从0开始的。
方便直接根据下表进行数组元素的访问，数组的元素是不能删的，只能覆盖，增删只能移动其他元素。
注意：
如果使⽤C++的话，要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器， 不是数组（来自代码随想录）
说到数组在代码考察中还是比较基础的：像二分查找、双指针！滑动窗口等（模拟的话对于我来说就是难题了，就暂时不考虑了）
①二分查找
这道题⽬的前提是数组为有序数组，同时题⽬还强调数组中⽆重复元素，因为⼀旦有重复元素，使⽤⼆分查找法返 回的元素下标可能不是唯⼀的。这也是使用二分查找的一个前提条件吧！
⼆分查找涉及的很多的边界条件，逻辑⽐较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right) ，到底是 right = middle 呢，还是要 right = middle - 1 呢？
这个时候一定要注意你选择的区间是[ ] 还是[ )!!!
1.如果是 【】
while (left <= right) 要使⽤ <= ，因为left == right是有意义的
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]⼀定不是target，那么接 下来要查找的左区间结束下标位置就是 middle - 1
2.如果是【)
while (left < right)，这⾥使⽤ < ,因为left == right在区间[left, right)是没有意义的
if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻 找，⽽寻找区间是左闭右开区间，所以right更新为middle，即：下⼀个查询区间不会去⽐较nums[middle]
※我的建议是新手一定要区分三种情况，不要把等于号归于大于或者小于中
6.29 第二题
先附一个错误的答案。
如果将 <= 和 >= 分开处理，可能会导致在某些情况下错误地排除掉正确的解。例如，当 mid * mid == x 时，这正是我们想要的结果，如果将其与其他情况分开处理，可能会导致逻辑复杂化，增加出错的风险。
更多推荐
3
0- 0
已为社区贡献2条内容
所有评论(0)