【九月打卡】第21天 算法（4）

课程名称：2周刷完100道前端优质面试真题
课程章节：第2章 前端面试技能拼图1 ：数据结构和算法（上），大厂面试必考
主讲老师：双越
课程内容：
今天学习的内容包括：
2-15 用 JS 实现二分查找-分析时间复杂度
2-16 用 JS 实现二分查找-代码演示和单元测试
2-17 用 JS 实现二分查找-递归和循环哪个更好
这几节主要是讲二分查找是啥，时间复杂度，两种实现方式和比较。

课程收获：
主要内容大致复述如下。

• 二分查找

用于已排序的数据。

假设表中元素是按升序排列，中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

• 循环写法

这个非常常见了，基本按照定义写就行。注意取中间值的 Math.floor 和 边界判断。

  const search = (arr, target) => {
    const len = arr.length;
    if (len) {
      let l = 0, r = len - 1;
      while (l <= r) {
        let mid = Math.floor((l + r) / 2);
        if (target === arr[mid]) {
          return mid;
        } else if (target > arr[mid]) {
          l = mid + 1;
        } else {
          r = mid - 1;
        }
      }
      return -1;
    } else {
      return -1;
    }
  };
  const arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120];
  const target = 40;
  console.info("二分结果", search(arr, target));

• 递归写法

每次比较中间位置记录的关键字与查找关键字，如果不相等，则修改范围再次调用。

  const search1 = (arr, target, l, r) => {
    const len = arr.length;
    if (!len || l > r) return -1;
    if (l == null) l = 0;
    if (r == null) r = len - 1;
    const m = Math.floor((l + r) / 2);
    if (target === arr[m]) {
      return m;
    } else if (target > arr[m]) {
      return search1(arr, target, m + 1, r);
    } else {
      return search1(arr, target, l, m - 1);
    }
  };

• 递归和循环哪个快

时间复杂度都是O(logn)
console.time 实际测试结果循环更快。
原因：递归增加了函数调用次数。

以上，结束。