使用二分法的前提是, 目标数组的元素必须是有序排列的, 所以二分法属于有序查找算法
二分法又称为 "折半查找", 从数组的中间节点开始查找, 将数组分为两部分
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;
- }
- }
用二分法遇到最坏的情况, 需要 6 次 还是 7 次?
如果只俩个球, 怎么才能用最少的次数, 找到临界点?
来源: http://www.qdfuns.com/issue/51273/73e7447af840d8a0fcd52937b343f678.html