政务网站建设信息,嵊州网站制作,台州椒江网站建设,找广网背景#xff1a;
在写力扣题目“搜素插入位置 ”时#xff0c;发现二分法的一个细节点#xff0c;打算记录下来#xff0c;先看一张图#xff1a; 我们知道#xff0c;排序数组#xff0c;更高效的是二分查找法~~~而二分法就是切割中间#xff0c;定义left是最开始的
在写力扣题目“搜素插入位置 ”时发现二分法的一个细节点打算记录下来先看一张图 我们知道排序数组更高效的是二分查找法~~~而二分法就是切割中间定义left是最开始的也就是下标为0right 是最后一个
那么这个mid到底怎么写
简单想到的是int mid (left right) / 2;
但是还有更好的写法那就是int mid left (right - left) / 2
原因解析
1. 防止整数溢出关键原因
假设
left 2000000000right 2100000000 21亿
使用 (left right) / 2的情况下
left right 2000000000 2100000000 4100000000
但 int 最大只能存储 2147483647约21亿会导致整数溢出变成负数
使用 left (right - left) / 2的情况下
right - left 100000000
(right - left)/2 50000000
left 50000000 2050000000
完全不会溢出 2. 数学等价性
两者数学上是等价的 left (right - left)/2 left right/2 - left/2 left/2 right/2 (left right)/2 但计算机的整数运算会截断小数所以写法不同会影响结果。
对比总结
写法安全性可读性推荐度(left right)/2可能溢出更直观❌ 不推荐left (right - left)/2绝对安全稍复杂✅ 推荐 案例题目练习
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
示例 1: 输入: nums [1,3,5,6], target 5 输出: 2 代码实现
class Solution {public int searchInsert(int[] nums, int target) {int left 0, right nums.length - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {return mid;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return left;}
}
