704. 二分查找
题目链接：https://leetcode.cn/problems/binary-search/
0x1 看到题目的第一想法
- 使用二分查找
0x2 自己实现过程中遇到哪些困难
- 用Python做题有点手生
- while循环条件一开始写错了，应该是用左右区间下标来进行判断
0x3 今日学习的文章链接，或者视频链接
0x4 看完代码随想录之后的想法
- 二分法看着简单，但是有许多坑，需要注意一下，动手写才知道哪里不会。
0x5 今日收获，记录一下自己的学习时长
- 二分法的使用条件
- 数组有序
- 数组中无重复元素
- 使用二分法
- 定义targeted查找的区间是左闭右闭或者左闭右开
- 在整个循环期间都需要保持这个定义的区间不变
- 左闭右闭 模版
1
2
3
4
5
6
7
8
9
10
11## 定义target在[left, right]可以找到
while(left <= right): # 此处left = right 有意义
mid = int((left + right) / 2)
if(nums[mid] < target): # target在右半区间[mid + 1, right]
left = mid + 1
elif(nums[mid] > target): # target在左半区间[left, mid + 1]
right = mid - 1
else:
return mid
return -1 - 时长
- 40min
0x6 类似题目
35.搜索插入位置
- https://leetcode.cn/problems/search-insert-position/description/
- 左闭右闭只需修改最后的return -1
[34].在排序数组中查找元素的第一个和最后一个位置
0x1 看到题目的第一想法
- 用三次二分查找，先找target，再找左边界和右边界
0x2 自己实现过程中遇到哪些困难
- 分析困难
- if里面不知道填什么
0x4 看完代码随想录之后的想法
- 充分分析可能出现的所有结果，并进行判断
27. 移除元素
题目链接：https://leetcode.cn/problems/remove-element/
0x1 看到题目的第一想法
- 删除数组元素，不能使用额外空间
- 快慢指针
0x2 自己实现过程中遇到哪些困难
- 大概没有
0x3 今日学习的文章链接，或者视频链接
0x4 看完代码随想录之后的想法
- 在数组、链表中很多时候都会用到这个快慢指针
- fast走在前面进行查找
- slow用来指向最终的结果数组
- 二维循环降到一维的常用方法
0x5 今日收获，记录一下自己的学习时长
- 数组或者链表在很多时候都会有用到快慢指针，会保持数组原来元素的相对位置，时间复杂度和空间复杂度都是O(1)
- 时长
- 20min
待重点复习
34
总结
- 数据结构基础
- 数组
- 下标从0开始
- 内存连续存放
- 数组
技巧
二分查找
- 数组有序
- 时间复杂度 O(logn)
快慢指针
- 降二维循环为一维
- 结果数组中的数据保持相对位置
- 时间复杂度 空间复杂度均为O(1)