黑马程序员技术交流社区

标题: [广州前端]"所谓"的前端算法（二） [打印本页]

---

作者: 黑黑黑黑黑黑    时间: 2018-2-1 11:18
标题: [广州前端]"所谓"的前端算法（二）
检索算法

二分查找算法：也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

查找说明

1.将数组的第一个位置设置为下边界（0）
2.将数组最后一个元素所在的位置设置为上边界（数组的长度减1）。
3.若下边界等于或小于上边界，则做如下操作。

• 将中点设置为（上边界加上下边界）除以2
• 如果中点的元素小于查询的值，则将下边界设置为中点元素所在下标加1
• 如果中点的元素大于查询的值，则将上边界设置为中点元素所在下标减1
• 否则中点元素即为要查找的数据，可以进行返回。
  

注意这里的数组必须是有序的

[JavaScript] 纯文本查看 复制代码

function binSearch(arr, data) {

  var upperBound = arr.length - 1;

  var lowerBound = 0;

  while (lowerBound <= upperBound) {

      var mid = Math.floor((upperBound + lowerBound) / 2);

      if (arr[mid] < data) {

          lowerBound = mid + 1;

      }

      else if(arr[mid] > data) {

          upperBound = mid - 1;

      } else {

          return mid;

      }

  }

  return -1;

}

二叉树算法

二叉树
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的特性

• 每个结点最多有两颗子树，结点的度最大为2
• 左子树和右子树是有顺序的，次序不能颠倒
• 即使某结点只有一个子树，也要区分左右子树。
  

二叉树遍历

这里采用递归-先序遍历一个树形结构

[JavaScript] 纯文本查看 复制代码

var preOrder = function (node) {

  if (node) {

    console.log(node.value);

    preOrder(node.left);

    preOrder(node.right);

  }

}

点击查看更多精彩前端资源

点击有惊喜

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2