二分查找实现两数相除的算法
- Ⅰ、两数相除：
- 1、题目描述：
- 2、解题思路：
- 3、实现代码：
- Ⅱ、小结：
Ⅰ、两数相除：
1、题目描述：
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使⽤乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其⼩数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输⼊: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333…) = truncate(3) = 3
示例 2:
输⼊: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333…) = -2
提示：
被除数和除数均为 32 位有符号整数。 除数不为 0。 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
2、解题思路：
思路一：
符合直觉的做法是：减数⼀次⼀次减去被减数，不断更新差，直到差⼩于 0，我们减了多少次，结果就是多少。
// 核心代码：此时的 dividend 是指被除数，divisor 是指除数;
// 最后的返回值 count 表示：在 dividend 内有多少个 divisor;
let acc = divisor;
let count = 0;
while (dividend - acc >= 0) {acc += divisor;count++;
}
return count;思路二、
思路一的做法简单直观，但是性能却⽐较差；
我们可以采用性能更好的⽅法：使⽤⼆分法来解决，性能有很⼤的提升;
二分法的本质：有序数组查找指定的值；
3、实现代码：
其一、代码为：
const divide = (dividend, divisor) => {if (divisor === 1) return dividend// 这种⽅法很巧妙，即符号相同则为正，不同则为负const isNegative = dividend > 0 !== divisor > 0// 此时利用异或，也能获取数据最后的符号值(即：isNegative 值);//const isNegative = dividend ^ (divisor < 0)// Math.pow(2, 31) 是指：计算 2 的 31 次方;const MAX_INTERGER = Math.pow(2, 31)// Math.abs(dividend) 是指：是计算 dividend 的绝对值(即：是 JavaScript 中的一个内置函数，用于取数的绝对值);const res = helper(Math.abs(dividend), Math.abs(divisor))// overflowif (res > MAX_INTERGER - 1 || res < -1 * MAX_INTERGER) {return MAX_INTERGER - 1}// 此时是：返回最终的结果;return isNegative ? -1 * res : res
}const helper = (dividend, divisor) => {// 若被除数小于等于 0，返回0;if (dividend <= 0) return 0// 若被除数小于除数，返回 0;if (dividend < divisor) return 0// 若除数等于 1，返回除数;if (divisor === 1) return dividend// ⼆分法let acc = 2 * divisorlet count = 1while (dividend - acc > 0) {// acc 一直 2 倍的增加，直到找到二分法的临界值;acc += acc// count 也会跟着 acc 值 2 倍的增加，并记录到二分法的临界值时，已有多少个 divisor 值被整除;count += count}// 直接使⽤位移运算，⽐如acc >> 1会有问题;// Math.floo() 函数：向下取整，即去掉小数部分，取整数部分;// last 代表：减去二分法临界值后剩余的值(即：准备再递归二分法的被除数值);const last = dividend - Math.floor(acc / 2)// 递归二分法的操作(除数不变，被除数更新);// 递归的出口：其一、last 值为负值； 其二、last 值小于 divisor 值;return count + helper(last, divisor)
}divide(86, 4)执行 divide(86, 4) 函数后代码执行的过程：第一次调用 helper(86,4) 函数：dividend(被除数) acc count86 4*2=8 186-8=78>0 8*2=16 1*2=286-16=70>0 16*2=32 2*2=486-32=54>0 32*2=64 4*2=886-64=22>0 64*2=128 8*2=1686-128=-42<0 128 16const last = 86 - 128/2(向下取整) = 86-64 = 22return 16 + helper(22,4)第二次调用 helper(22,4) 函数：dividend(被除数) acc count22 4*2=8 122-8=14>0 8*2=16 1*2=222-16=6>0 16*2=32 2*2=422-32=-10<0 32 4const last = 22 - 32/2(向下取整) = 22-16 = 6return 4 + helper(6,4)第三次调用 helper(6,4) 函数：dividend(被除数) acc count6 4*2=8 16-8=-2<0 8 1const last = 6 - 8/2(向下取整) = 6-4 = 2return 1 + helper(2,4)第四次调用 helper(2,4) 函数：return 0注意：此时的 return 值是递归的，递归后最终的返回值为：return 16 + 4 + 1 + 0 = 21其二、截图为：
Ⅱ、小结：
其一、哪里有不对或不合适的地方，还请大佬们多多指点和交流！
其二、若有转发或引用本文章内容，请注明本博客地址(直接点击下面 url 跳转) https://blog.csdn.net/weixin_43405300,创作不易，且行且珍惜！
其三、有兴趣的话，可以多多关注这个专栏(Vue(Vue2+Vue3)面试必备专栏)(直接点击下面 url 跳转)：https://blog.csdn.net/weixin_43405300/category_11525646.html?spm=1001.2014.3001.5482
