文章目录
- 二分法
- 704 二分查找
- 思路
- 35.搜索插入位置
- 四种情况
- 思路一
- 思路二
- 34. 在排序数组中查找元素的第一个和最后一个位置✨
- 关键在于分析一些细节
- 解析看代码注释
- 总结二分法
二分法
来自leetcode
704 二分查找
思路
- 利用在右指针：设置target可选范围
- 比较目标值 和 中间值 来缩小可选范围
- 找到目标值 返回下标 没找到 返回 -1
本体较为简单，主要是二分的方法要知道，以及 可选区间的开闭
/*
* @lc app=leetcode.cn id=704 lang=javascript
*
* [704] 二分查找
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
let left = 0, right = nums.length - 1
while(left <= right) {
let mid = left + Math.floor((right - left)/2)
if(target > nums[mid]) {
left = mid + 1
} else if(target < nums[mid]) {
right = mid - 1
} else {
return mid
}
}
return -1
};
// @lc code=end
35.搜索插入位置
四种情况
- 目标值在数组所有元素之前
- 目标值等于数组中某一个元素
- 目标值插入数组中的位置
- 目标值在数组所有元素之后
思路一
二分法 找目标值
- 找到就是按照二分查找的方法
- 没找到：插入元素
- 在可选范围里面: 举例分析插在mid后面即可
- 如果不在范围内 就两端位置
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
let left = 0, right = nums.length - 1
let ant
if(target < nums[0]) return 0
if(target > nums[nums.length - 1]) return nums.length
while (left <= right) {
let mid = left + Math.floor((right - left)/2)
if(nums[mid] > target) {
right = mid -1
} else if (nums[mid] < target) {
left = mid + 1
ant = left
} else {
return mid
}
}
return ant
};
思路二
重点代码注释
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
// 开始还是二分查找 缩小区间
// 找得到目标就是索引
// 找不到目标值 插入地方：与mid比较，最后位置肯定会取代mid
// 当正好到< mid1 > mid2时，位置就确定好了 mid1
// 注意ant初始值
// 为什么初始值是nums.length:因为当target>nums[mid]一致都大于的时候，我们这里就直接放在末尾，也就是ant初始值
let left = 0, right = nums.length - 1
let ant = nums.length
while(left <= right) {
const mid = left + Math.floor((right - left) / 2)
if(target > nums[mid]) left = mid + 1
else if (target < nums[mid]) {
ant = mid
right = mid - 1
}
else return mid
}
return ant
};
34. 在排序数组中查找元素的第一个和最后一个位置✨
关键在于分析一些细节
- 左右边界分开查找使用二分
- target的三种情况划分
- 临界值的设置也很关键，为什么不是-1，而是-2
- 我们这里的设置的边界值不包括target，为什么不包括
解析看代码注释
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
// -1 -2 0 0 0 4 5 8
var searchRange = function(nums, target) {
// 左右边界分开找
/**
三种情况：1 target范围在最左边最右边 不存在目标值 返回[-1,-1]
2 target范围在中间 但不存在目标值 返回[-1,-1]
3 target在范围里面且存在 返回 位置下标
*/
/**
我们这里的设置的边界值不包括target，为什么不包括？
如果只有一个符合条件的时候，我们此时lB,rB也不会重合相等
如果重合相等说明了没有目标值，也就是我们的情况二
边界值初始值为什么不是-1？
因为如果-1，在最左边是可能存在target的（[3,3,4,5] target = 3，此时lB = -1），所以我们设为-2
*/
// 左边界： mid 位置 一直 >= target 最终，到临界值是就是左边界
// (左边界)target ... target mid
const getLeftBorder = function(nums, target) {
let left = 0, right = nums.length -1, lB = -2
while(left <= right) {
let mid = left + Math.floor((right - left)/2)
if(nums[mid] >= target) {
right = mid - 1
lB = right
} else left = mid + 1
}
return lB
}
// 右边界： mid 位置 一直 <= target 最终，到临界值是就是右边界
// mid target ... target(右边界)
const getRightBorder = function(nums, target) {
let left = 0, right = nums.length - 1, rB = -2
while(left <= right) {
let mid = left + Math.floor((right - left)/2)
if(nums[mid] <= target) {
left = mid + 1
rB = left
} else right = mid - 1
}
return rB
}
// 调用函数
let lB = getLeftBorder(nums,target)
let rB = getRightBorder(nums,target)
// 情况一 目标值无 且在数组范围外
if(lB == -2 || rB == -2) return [-1,-1]
// 情况三 目标值右，且个数大于等于1 lB target ... target rB
if(rB - lB > 1) return [lB + 1, rB - 1]
// 情况二 目标值无，在数组范围内
return [-1,-1]
};
总结二分法
- 二分法的基本使用看706：二分查找即可
- 使用条件：有序数组，无重复元素
- 要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
- 区间：左闭右闭即[left, right]，或者左闭右开即[left, right)
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
- while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
- 操作: 设置一个中间值,与目标值对比,改变区间的边界,选择新的区间,循环
