前端面试 - 算法篇(二分法)

发布日期:2019-05-05

前段时间换了份工作,也经历了很多面试,最终通常都会扑在算法上

虽说前端是所有程序员中,对于算法的要求最低的一个岗位,但算法依旧是进阶的必修课

于是决定记录一下与算法相关的面试题,以后拿去面别人

 

一、面试题

问:有一个一百层的高楼,现在给你两个完全一样的玻璃球,去测出在哪一层楼把球扔出去,刚好能把玻璃球砸碎?

答:emmmmmm

问:球碎了就没法用了

答:那如果没碎呢?

问:emmmmmm

答:啊哈,那就拿着球从一楼往上,一层一层的试呗~

问:好,那现在不限制球的数量,但要求用最少的次数,去找到这个临界点

答:二分法!从中间的楼层开始扔球,如果碎了就在下面的楼层中继续找

问:没错,二分法是最快的解决方案,但如果遇到最差的情况,需要用几个球呢?

答:我数一数

问:……

答:……

问:算了,下一个问题吧

 

二、二分法

使用二分法的前提是,目标数组的元素必须是有序排列的,所以二分法属于有序查找算法

二分法又称为“折半查找”,从数组的中间节点开始查找,将数组分为两部分

如果目标元素和中间节点不相等,就通过比较两者的大小,确定接下来查找数组的前半部分还是后半部分

然后递归查找,直到找到目标元素,或者发现目标元素不在数组内

在最坏的情况下,需要的次数为:(logn)+1 ,其中 log2n 向下取整

function BinarySearch(arr target) { let s = 0 let e = arr.length - 1 let m = Math.floor((s + e) / 2) let trun = arr[s] <= arr[e] //确定排序顺序 while (s < e && arr[m] !== target) { if (arr[m] > target) { trun ? (e = m - 1) : (s = m + 1) } else { trun ? (s = m + 1) : (e = m - 1) } m = Math.floor((s + e) / 2) } if (arr[m] == target) { console.log("找到了位置%s" m t) return m } else { console.log("没找到" t) return -1 }}

 

三、问题拓展

1. 用二分法遇到最坏的情况,需要 6 次 还是 7 次?

2. 如果只有两个球,怎么才能用最少的次数,找到临界点?