注意事项
- left<=right,等于不能漏掉,定位到同一个元素的时候也要判断和target是否相等
- left=mid+1,right=mid-1而不能是mid,否则会死循环,比如nums={1,2},target=2,此时mid就会一直指向1。
补充:
- 数组为有序数组,同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件
- 此处对应的是左闭右闭区间,还有左闭右开区间的写法,主要就是遵循循环不变量规则。
- 思考了很久的原地删除操作,原来是用双指针来的。
- 我想到同O(n)也可用差分解决,不过更麻烦还要O(n)的空间大小,显然不太行。
- 暴力也可接受,但仍然双指针解决最佳
- 收缩窗口,维护最小数组应该用while而不是if,因为新来的元素可能一个顶几个。比如nums={1,1},target=3,新来的为3,就可以把前面的1,1都扔掉。