常用算法模板（一）

二分查找

适用场景：

• 有序表中；
• 可经排序后形成有序表。

  // 二分法查找target
  const binarySearch = (arr, target) => {
      // 左闭右开区间
      let left = 0;
      let right = arr.length;
  
      while (left < right) {
          let mid = left + Math.floor((right - left) / 2);
          // 注意写正确if条件中的语句，满足条件的mid值放入左区间
          if (arr[mid] < target) {
              left = mid + 1;
          }
          else {
              right = mid;
          }
      }
  
      // 此时left,right相等，位于右区间的最左边
      // 如果不确定target值是否存在，则最后返回前比较一下arr[left]与target值是否相等
      return left;
  }

BFS

适用场景：

• 遍历树、图时；
• 求某个“最少/短值”时（最短路径问题）；
• 树的层序遍历。

  // 递归实现略
  
  // 遍历图，寻找到target的最短路径，迭代实现
  const bfs = (root, target) => {
      const queue = [root];
      // 图中存在环时，需要申请哈希集记录遍历过的节点，以免节点重复入队造成死循环
      const set = new Set(root);
      // 最短路径问题需要返回步长
      let step = -1;
  
      while (queue.length) {
          ++step;
          const size = queue.length;
          for (i = 0; i < size; ++i) {
              // 队首节点出队
              const cur = queue.shift();
              if (cur === target) {
                  return step;
              }
              // 遍历当前节点的下一层节点
              for (let next in cur.nextNodes) {
                  if (!set.has(next)) {
                      queue.push(next);
                      set.add(next);
                  }
              }
          }
      }
  
      return -1;
  }

DFS

适用场景：

• 类似BFS，一般的树/图遍历会选择DFS，符合人类的思维习惯。

  // 递归实现略
  
  // 遍历图寻找target，迭代实现
  const dfs = (root, target) => {
      // bfs使用队列，dfs使用栈
      const stack = [root];
      // 图中存在环时，需要申请哈希集记录遍历过的节点，以免节点重复入队造成死循环
      const set = new Set(root);
  
      while (stack.length) {
          // 栈顶节点出栈
          const cur = stack.pop();
          if (cur === target) {
              return true;
          }
          // 遍历当前节点的下一层节点
          for (let next in cur.nextNodes) {
              if (!set.has(next)) {
                  stack.push(next);
                  set.add(next);
              }
          }
      }
  
      return false;
  }