1. 题目
2. 读题(需要重点注意的东西)
思路(二分):
二分的核心是找出一个分界点,如果左右两段有不同的性质,二分就能给它找出来。
二分的模板有两种可能的情况
① 当 l = mid时,else后的 r 一定等于mid - 1, 上面的mid在 l + r 的基础上也要+1;总结成下方这段模板;
while(l < r){
int mid = l + r + 1 >> 1;
if(判断语句) l = mid;
else r = mid - 1;
}
② 当r = mid时,else后的 l 一定等于mid + 1, 上面的mid就为 l + r,不需要加1;总结成下方这段模板。
while(l < r){
int mid = l + r >> 1;
if(判断语句) r = mid;
else l = mid + 1;
}
3. 解法
---------------------------------------------------解法---------------------------------------------------:
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
// 要放到最后一位的情况
if(l == nums.length - 1 && nums[l] < target) return nums.length;
// 要放到第一位的情况
else if(l == 0 && nums[l] > target) return 0;
return l;
}
}
可能存在的问题:
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
- 二分