前端面试之算法二分法

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

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

image.png

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

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

在最坏的情况下，需要的次数为：(log2 n)+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. 如果只俩个球，怎么才能用最少的次数，找到临界点？
   欢迎加入全栈开发交流群一起学习交流：864305860