二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。
英语科普:二分法,dichotomy。
目录
一、前提
数组已预先排序。
二、具体实现
问题:在已从小到大排序的数组(数组内元素均为数字)中找到给定的数字对应的下标。
回答:
function dichotomySearch (arr, num) { var low = 0 var high = arr.length - 1 var mid = Math.floor((low + high) / 2) // while循环的判断条件是high - low > 1 while (high - low > 1) { if (num === arr[low]) { return low } else if (num === arr[high]) { return high } else if (num === arr[mid]) { return mid } else if (num > arr[mid]) { low = mid mid = Math.floor((low + high) / 2) } else { high = mid mid = Math.floor((low + high) / 2) } } // 如果没找到,则返回-1 return -1 }
三、求平方根
求一个数n的平方根。
/** * 计算平方根 * @param {[type]} n 需要求平方根的目标数字 * @param {[type]} deviation 偏离度(允许的误差范围) * @return {[type]} 返回平方根 */ function square (n, deviation) { let max = n let min = 0 let mid = (max - min) / 2 const isAlmost = (val) => (val * val - n <= deviation) && (n - val * val <= deviation) while (isAlmost(mid) === false) { if (mid * mid > n) { max = mid mid = (max + min) / 2 } else if (mid * mid < n) { min = mid mid = (max + min) / 2 } } return mid }