前端面试之算法二分法

原创 年树先生 随笔 前端面试 11377阅读 24 天前 举报

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

二分法又称为“折半查找”,从数组的中间节点开始查找,将数组分为两部分
image.png
如果目标元素和中间节点不相等,就通过比较两者的大小,确定接下来查找数组的前半部分还是后半部分

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

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

  1. 用二分法遇到最坏的情况,需要 6 次 还是 7 次?
  2. 如果只俩个球,怎么才能用最少的次数,找到临界点?
    欢迎加入全栈开发交流群一起学习交流:864305860
评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复