1. 题目
2. 读题(需要重点注意的东西)
思路(二分):
二分的核心是找出一个分界点,如果左右两段有不同的性质,二分就能给它找出来。
解题思路:
用二分找出第一个target—if(nums[mid] >= target)
再用二分找出第二个target—if(nums[mid] <= target)
二分的模板有两种可能的情况
① 当 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[] searchRange(int[] nums, int target) {
int[] res = {-1,-1};
if(nums.length == 0) return res;
// 查起始位置
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(nums[l] == target) res[0] = l;
else return res;
// 查找终止位置
l = 0;
r = nums.length - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] <= target) l = mid;
else r = mid - 1;
}
res[1] = l;
return res;
}
}
可能存在的问题:
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
- 二分